X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FTransforms%2FIPO%2FFunctionAttrs.cpp;h=30c0b3a1763300d533698c5a6beade3cc8d22361;hp=45bb488cf6bf30214eb52960025c65092629d613;hb=821e7c773781472bd1fa3fa34a4e8ff477f90548;hpb=876ac60880843f37c25ec03e46eb73b8e197e971

diff --git a/lib/Transforms/IPO/FunctionAttrs.cpp b/lib/Transforms/IPO/FunctionAttrs.cpp
index 45bb488cf6b..30c0b3a1763 100644
--- a/lib/Transforms/IPO/FunctionAttrs.cpp
+++ b/lib/Transforms/IPO/FunctionAttrs.cpp
@@ -18,136 +18,84 @@
 //
 //===----------------------------------------------------------------------===//
 
-#define DEBUG_TYPE "functionattrs"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/ADT/SCCIterator.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/CallGraphSCCPass.h"
 #include "llvm/Analysis/CaptureTracking.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
-#include "llvm/Target/TargetLibraryInfo.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
 using namespace llvm;
 
+#define DEBUG_TYPE "functionattrs"
+
 STATISTIC(NumReadNone, "Number of functions marked readnone");
 STATISTIC(NumReadOnly, "Number of functions marked readonly");
 STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
 STATISTIC(NumReadNoneArg, "Number of arguments marked readnone");
 STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly");
 STATISTIC(NumNoAlias, "Number of function returns marked noalias");
+STATISTIC(NumNonNullReturn, "Number of function returns marked nonnull");
 STATISTIC(NumAnnotated, "Number of attributes added to library functions");
 
 namespace {
-  struct FunctionAttrs : public CallGraphSCCPass {
-    static char ID; // Pass identification, replacement for typeid
-    FunctionAttrs() : CallGraphSCCPass(ID), AA(0) {
-      initializeFunctionAttrsPass(*PassRegistry::getPassRegistry());
-    }
-
-    // runOnSCC - Analyze the SCC, performing the transformation if possible.
-    bool runOnSCC(CallGraphSCC &SCC);
-
-    // AddReadAttrs - Deduce readonly/readnone attributes for the SCC.
-    bool AddReadAttrs(const CallGraphSCC &SCC);
-
-    // AddArgumentAttrs - Deduce nocapture attributes for the SCC.
-    bool AddArgumentAttrs(const CallGraphSCC &SCC);
-
-    // IsFunctionMallocLike - Does this function allocate new memory?
-    bool IsFunctionMallocLike(Function *F,
-                              SmallPtrSet<Function*, 8> &) const;
-
-    // AddNoAliasAttrs - Deduce noalias attributes for the SCC.
-    bool AddNoAliasAttrs(const CallGraphSCC &SCC);
-
-    // Utility methods used by inferPrototypeAttributes to add attributes
-    // and maintain annotation statistics.
-
-    void setDoesNotAccessMemory(Function &F) {
-      if (!F.doesNotAccessMemory()) {
-        F.setDoesNotAccessMemory();
-        ++NumAnnotated;
-      }
-    }
-
-    void setOnlyReadsMemory(Function &F) {
-      if (!F.onlyReadsMemory()) {
-        F.setOnlyReadsMemory();
-        ++NumAnnotated;
-      }
-    }
-
-    void setDoesNotThrow(Function &F) {
-      if (!F.doesNotThrow()) {
-        F.setDoesNotThrow();
-        ++NumAnnotated;
-      }
-    }
-
-    void setDoesNotCapture(Function &F, unsigned n) {
-      if (!F.doesNotCapture(n)) {
-        F.setDoesNotCapture(n);
-        ++NumAnnotated;
-      }
-    }
-
-    void setOnlyReadsMemory(Function &F, unsigned n) {
-      if (!F.onlyReadsMemory(n)) {
-        F.setOnlyReadsMemory(n);
-        ++NumAnnotated;
-      }
-    }
-
-    void setDoesNotAlias(Function &F, unsigned n) {
-      if (!F.doesNotAlias(n)) {
-        F.setDoesNotAlias(n);
-        ++NumAnnotated;
-      }
-    }
-
-    // inferPrototypeAttributes - Analyze the name and prototype of the
-    // given function and set any applicable attributes.  Returns true
-    // if any attributes were set and false otherwise.
-    bool inferPrototypeAttributes(Function &F);
+struct FunctionAttrs : public CallGraphSCCPass {
+  static char ID; // Pass identification, replacement for typeid
+  FunctionAttrs() : CallGraphSCCPass(ID) {
+    initializeFunctionAttrsPass(*PassRegistry::getPassRegistry());
+  }
 
-    // annotateLibraryCalls - Adds attributes to well-known standard library
-    // call declarations.
-    bool annotateLibraryCalls(const CallGraphSCC &SCC);
+  bool runOnSCC(CallGraphSCC &SCC) override;
 
-    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
-      AU.setPreservesCFG();
-      AU.addRequired<AliasAnalysis>();
-      AU.addRequired<TargetLibraryInfo>();
-      CallGraphSCCPass::getAnalysisUsage(AU);
-    }
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesCFG();
+    AU.addRequired<AssumptionCacheTracker>();
+    AU.addRequired<TargetLibraryInfoWrapperPass>();
+    CallGraphSCCPass::getAnalysisUsage(AU);
+  }
 
-  private:
-    AliasAnalysis *AA;
-    TargetLibraryInfo *TLI;
-  };
+private:
+  TargetLibraryInfo *TLI;
+
+  bool AddReadAttrs(const CallGraphSCC &SCC);
+  bool AddArgumentAttrs(const CallGraphSCC &SCC);
+  bool IsFunctionMallocLike(Function *F, SmallPtrSet<Function *, 8> &) const;
+  bool AddNoAliasAttrs(const CallGraphSCC &SCC);
+  bool ReturnsNonNull(Function *F, SmallPtrSet<Function *, 8> &,
+                      bool &Speculative) const;
+  bool AddNonNullAttrs(const CallGraphSCC &SCC);
+  bool inferPrototypeAttributes(Function &F);
+  bool annotateLibraryCalls(const CallGraphSCC &SCC);
+};
 }
 
 char FunctionAttrs::ID = 0;
 INITIALIZE_PASS_BEGIN(FunctionAttrs, "functionattrs",
-                "Deduce function attributes", false, false)
-INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
+                      "Deduce function attributes", false, false)
+INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
+INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_END(FunctionAttrs, "functionattrs",
-                "Deduce function attributes", false, false)
+                    "Deduce function attributes", false, false)
 
 Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); }
 
-
-/// AddReadAttrs - Deduce readonly/readnone attributes for the SCC.
+/// Deduce readonly/readnone attributes for the SCC.
 bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) {
-  SmallPtrSet<Function*, 8> SCCNodes;
+  SmallPtrSet<Function *, 8> SCCNodes;
 
   // Fill SCCNodes with the elements of the SCC.  Used for quickly
   // looking up whether a given CallGraphNode is in this SCC.
@@ -160,12 +108,21 @@ bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) {
   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
     Function *F = (*I)->getFunction();
 
-    if (F == 0)
-      // External node - may write memory.  Just give up.
+    if (!F || F->hasFnAttribute(Attribute::OptimizeNone))
+      // External node or node we don't want to optimize - assume it may write
+      // memory and give up.
       return false;
 
-    AliasAnalysis::ModRefBehavior MRB = AA->getModRefBehavior(F);
-    if (MRB == AliasAnalysis::DoesNotAccessMemory)
+    // We need to manually construct BasicAA directly in order to disable its
+    // use of other function analyses.
+    BasicAAResult BAR(createLegacyPMBasicAAResult(*this, *F));
+
+    // Construct our own AA results for this function. We do this manually to
+    // work around the limitations of the legacy pass manager.
+    AAResults AAR(createLegacyPMAAResults(*this, *F, BAR));
+
+    FunctionModRefBehavior MRB = AAR.getModRefBehavior(F);
+    if (MRB == FMRB_DoesNotAccessMemory)
       // Already perfect!
       continue;
 
@@ -191,7 +148,7 @@ bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) {
         // Ignore calls to functions in the same SCC.
         if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction()))
           continue;
-        AliasAnalysis::ModRefBehavior MRB = AA->getModRefBehavior(CS);
+        FunctionModRefBehavior MRB = AAR.getModRefBehavior(CS);
         // If the call doesn't access arbitrary memory, we may be able to
         // figure out something.
         if (AliasAnalysis::onlyAccessesArgPointees(MRB)) {
@@ -203,14 +160,15 @@ bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) {
                  CI != CE; ++CI) {
               Value *Arg = *CI;
               if (Arg->getType()->isPointerTy()) {
-                AliasAnalysis::Location Loc(Arg,
-                                            AliasAnalysis::UnknownSize,
-                                            I->getMetadata(LLVMContext::MD_tbaa));
-                if (!AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) {
-                  if (MRB & AliasAnalysis::Mod)
+                AAMDNodes AAInfo;
+                I->getAAMetadata(AAInfo);
+
+                MemoryLocation Loc(Arg, MemoryLocation::UnknownSize, AAInfo);
+                if (!AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) {
+                  if (MRB & MRI_Mod)
                     // Writes non-local memory.  Give up.
                     return false;
-                  if (MRB & AliasAnalysis::Ref)
+                  if (MRB & MRI_Ref)
                     // Ok, it reads non-local memory.
                     ReadsMemory = true;
                 }
@@ -219,30 +177,30 @@ bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) {
           continue;
         }
         // The call could access any memory. If that includes writes, give up.
-        if (MRB & AliasAnalysis::Mod)
+        if (MRB & MRI_Mod)
           return false;
         // If it reads, note it.
-        if (MRB & AliasAnalysis::Ref)
+        if (MRB & MRI_Ref)
           ReadsMemory = true;
         continue;
       } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
         // Ignore non-volatile loads from local memory. (Atomic is okay here.)
         if (!LI->isVolatile()) {
-          AliasAnalysis::Location Loc = AA->getLocation(LI);
-          if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true))
+          MemoryLocation Loc = MemoryLocation::get(LI);
+          if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
             continue;
         }
       } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
         // Ignore non-volatile stores to local memory. (Atomic is okay here.)
         if (!SI->isVolatile()) {
-          AliasAnalysis::Location Loc = AA->getLocation(SI);
-          if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true))
+          MemoryLocation Loc = MemoryLocation::get(SI);
+          if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
             continue;
         }
       } else if (VAArgInst *VI = dyn_cast<VAArgInst>(I)) {
         // Ignore vaargs on local memory.
-        AliasAnalysis::Location Loc = AA->getLocation(VI);
-        if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true))
+        MemoryLocation Loc = MemoryLocation::get(VI);
+        if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
           continue;
       }
 
@@ -275,11 +233,10 @@ bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) {
 
     // Clear out any existing attributes.
     AttrBuilder B;
-    B.addAttribute(Attribute::ReadOnly)
-      .addAttribute(Attribute::ReadNone);
-    F->removeAttributes(AttributeSet::FunctionIndex,
-                        AttributeSet::get(F->getContext(),
-                                          AttributeSet::FunctionIndex, B));
+    B.addAttribute(Attribute::ReadOnly).addAttribute(Attribute::ReadNone);
+    F->removeAttributes(
+        AttributeSet::FunctionIndex,
+        AttributeSet::get(F->getContext(), AttributeSet::FunctionIndex, B));
 
     // Add in the new attribute.
     F->addAttribute(AttributeSet::FunctionIndex,
@@ -295,124 +252,127 @@ bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) {
 }
 
 namespace {
-  // For a given pointer Argument, this retains a list of Arguments of functions
-  // in the same SCC that the pointer data flows into. We use this to build an
-  // SCC of the arguments.
-  struct ArgumentGraphNode {
-    Argument *Definition;
-    SmallVector<ArgumentGraphNode*, 4> Uses;
-  };
-
-  class ArgumentGraph {
-    // We store pointers to ArgumentGraphNode objects, so it's important that
-    // that they not move around upon insert.
-    typedef std::map<Argument*, ArgumentGraphNode> ArgumentMapTy;
-
-    ArgumentMapTy ArgumentMap;
-
-    // There is no root node for the argument graph, in fact:
-    //   void f(int *x, int *y) { if (...) f(x, y); }
-    // is an example where the graph is disconnected. The SCCIterator requires a
-    // single entry point, so we maintain a fake ("synthetic") root node that
-    // uses every node. Because the graph is directed and nothing points into
-    // the root, it will not participate in any SCCs (except for its own).
-    ArgumentGraphNode SyntheticRoot;
-
-  public:
-    ArgumentGraph() { SyntheticRoot.Definition = 0; }
-
-    typedef SmallVectorImpl<ArgumentGraphNode*>::iterator iterator;
-
-    iterator begin() { return SyntheticRoot.Uses.begin(); }
-    iterator end() { return SyntheticRoot.Uses.end(); }
-    ArgumentGraphNode *getEntryNode() { return &SyntheticRoot; }
-
-    ArgumentGraphNode *operator[](Argument *A) {
-      ArgumentGraphNode &Node = ArgumentMap[A];
-      Node.Definition = A;
-      SyntheticRoot.Uses.push_back(&Node);
-      return &Node;
-    }
-  };
+/// For a given pointer Argument, this retains a list of Arguments of functions
+/// in the same SCC that the pointer data flows into. We use this to build an
+/// SCC of the arguments.
+struct ArgumentGraphNode {
+  Argument *Definition;
+  SmallVector<ArgumentGraphNode *, 4> Uses;
+};
+
+class ArgumentGraph {
+  // We store pointers to ArgumentGraphNode objects, so it's important that
+  // that they not move around upon insert.
+  typedef std::map<Argument *, ArgumentGraphNode> ArgumentMapTy;
+
+  ArgumentMapTy ArgumentMap;
+
+  // There is no root node for the argument graph, in fact:
+  //   void f(int *x, int *y) { if (...) f(x, y); }
+  // is an example where the graph is disconnected. The SCCIterator requires a
+  // single entry point, so we maintain a fake ("synthetic") root node that
+  // uses every node. Because the graph is directed and nothing points into
+  // the root, it will not participate in any SCCs (except for its own).
+  ArgumentGraphNode SyntheticRoot;
+
+public:
+  ArgumentGraph() { SyntheticRoot.Definition = nullptr; }
+
+  typedef SmallVectorImpl<ArgumentGraphNode *>::iterator iterator;
+
+  iterator begin() { return SyntheticRoot.Uses.begin(); }
+  iterator end() { return SyntheticRoot.Uses.end(); }
+  ArgumentGraphNode *getEntryNode() { return &SyntheticRoot; }
+
+  ArgumentGraphNode *operator[](Argument *A) {
+    ArgumentGraphNode &Node = ArgumentMap[A];
+    Node.Definition = A;
+    SyntheticRoot.Uses.push_back(&Node);
+    return &Node;
+  }
+};
 
-  // This tracker checks whether callees are in the SCC, and if so it does not
-  // consider that a capture, instead adding it to the "Uses" list and
-  // continuing with the analysis.
-  struct ArgumentUsesTracker : public CaptureTracker {
-    ArgumentUsesTracker(const SmallPtrSet<Function*, 8> &SCCNodes)
+/// This tracker checks whether callees are in the SCC, and if so it does not
+/// consider that a capture, instead adding it to the "Uses" list and
+/// continuing with the analysis.
+struct ArgumentUsesTracker : public CaptureTracker {
+  ArgumentUsesTracker(const SmallPtrSet<Function *, 8> &SCCNodes)
       : Captured(false), SCCNodes(SCCNodes) {}
 
-    void tooManyUses() { Captured = true; }
+  void tooManyUses() override { Captured = true; }
 
-    bool captured(Use *U) {
-      CallSite CS(U->getUser());
-      if (!CS.getInstruction()) { Captured = true; return true; }
+  bool captured(const Use *U) override {
+    CallSite CS(U->getUser());
+    if (!CS.getInstruction()) {
+      Captured = true;
+      return true;
+    }
 
-      Function *F = CS.getCalledFunction();
-      if (!F || !SCCNodes.count(F)) { Captured = true; return true; }
+    Function *F = CS.getCalledFunction();
+    if (!F || !SCCNodes.count(F)) {
+      Captured = true;
+      return true;
+    }
 
-      bool Found = false;
-      Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end();
-      for (CallSite::arg_iterator PI = CS.arg_begin(), PE = CS.arg_end();
-           PI != PE; ++PI, ++AI) {
-        if (AI == AE) {
-          assert(F->isVarArg() && "More params than args in non-varargs call");
-          Captured = true;
-          return true;
-        }
-        if (PI == U) {
-          Uses.push_back(AI);
-          Found = true;
-          break;
-        }
+    bool Found = false;
+    Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end();
+    for (CallSite::arg_iterator PI = CS.arg_begin(), PE = CS.arg_end();
+         PI != PE; ++PI, ++AI) {
+      if (AI == AE) {
+        assert(F->isVarArg() && "More params than args in non-varargs call");
+        Captured = true;
+        return true;
+      }
+      if (PI == U) {
+        Uses.push_back(AI);
+        Found = true;
+        break;
       }
-      assert(Found && "Capturing call-site captured nothing?");
-      (void)Found;
-      return false;
     }
+    assert(Found && "Capturing call-site captured nothing?");
+    (void)Found;
+    return false;
+  }
 
-    bool Captured;  // True only if certainly captured (used outside our SCC).
-    SmallVector<Argument*, 4> Uses;  // Uses within our SCC.
+  bool Captured; // True only if certainly captured (used outside our SCC).
+  SmallVector<Argument *, 4> Uses; // Uses within our SCC.
 
-    const SmallPtrSet<Function*, 8> &SCCNodes;
-  };
+  const SmallPtrSet<Function *, 8> &SCCNodes;
+};
 }
 
 namespace llvm {
-  template<> struct GraphTraits<ArgumentGraphNode*> {
-    typedef ArgumentGraphNode NodeType;
-    typedef SmallVectorImpl<ArgumentGraphNode*>::iterator ChildIteratorType;
+template <> struct GraphTraits<ArgumentGraphNode *> {
+  typedef ArgumentGraphNode NodeType;
+  typedef SmallVectorImpl<ArgumentGraphNode *>::iterator ChildIteratorType;
 
-    static inline NodeType *getEntryNode(NodeType *A) { return A; }
-    static inline ChildIteratorType child_begin(NodeType *N) {
-      return N->Uses.begin();
-    }
-    static inline ChildIteratorType child_end(NodeType *N) {
-      return N->Uses.end();
-    }
-  };
-  template<> struct GraphTraits<ArgumentGraph*>
-    : public GraphTraits<ArgumentGraphNode*> {
-    static NodeType *getEntryNode(ArgumentGraph *AG) {
-      return AG->getEntryNode();
-    }
-    static ChildIteratorType nodes_begin(ArgumentGraph *AG) {
-      return AG->begin();
-    }
-    static ChildIteratorType nodes_end(ArgumentGraph *AG) {
-      return AG->end();
-    }
-  };
+  static inline NodeType *getEntryNode(NodeType *A) { return A; }
+  static inline ChildIteratorType child_begin(NodeType *N) {
+    return N->Uses.begin();
+  }
+  static inline ChildIteratorType child_end(NodeType *N) {
+    return N->Uses.end();
+  }
+};
+template <>
+struct GraphTraits<ArgumentGraph *> : public GraphTraits<ArgumentGraphNode *> {
+  static NodeType *getEntryNode(ArgumentGraph *AG) {
+    return AG->getEntryNode();
+  }
+  static ChildIteratorType nodes_begin(ArgumentGraph *AG) {
+    return AG->begin();
+  }
+  static ChildIteratorType nodes_end(ArgumentGraph *AG) { return AG->end(); }
+};
 }
 
-// Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone.
+/// Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone.
 static Attribute::AttrKind
 determinePointerReadAttrs(Argument *A,
-                          const SmallPtrSet<Argument*, 8> &SCCNodes) {
-                                                       
-  SmallVector<Use*, 32> Worklist;
-  SmallSet<Use*, 32> Visited;
-  int Count = 0;
+                          const SmallPtrSet<Argument *, 8> &SCCNodes) {
+
+  SmallVector<Use *, 32> Worklist;
+  SmallSet<Use *, 32> Visited;
 
   // inalloca arguments are always clobbered by the call.
   if (A->hasInAllocaAttr())
@@ -421,14 +381,9 @@ determinePointerReadAttrs(Argument *A,
   bool IsRead = false;
   // We don't need to track IsWritten. If A is written to, return immediately.
 
-  for (Value::use_iterator UI = A->use_begin(), UE = A->use_end();
-       UI != UE; ++UI) {
-    if (Count++ >= 20)
-      return Attribute::None;
-
-    Use *U = &UI.getUse();
-    Visited.insert(U);
-    Worklist.push_back(U);
+  for (Use &U : A->uses()) {
+    Visited.insert(&U);
+    Worklist.push_back(&U);
   }
 
   while (!Worklist.empty()) {
@@ -443,24 +398,36 @@ determinePointerReadAttrs(Argument *A,
     case Instruction::Select:
     case Instruction::AddrSpaceCast:
       // The original value is not read/written via this if the new value isn't.
-      for (Instruction::use_iterator UI = I->use_begin(), UE = I->use_end();
-           UI != UE; ++UI) {
-        Use *U = &UI.getUse();
-        if (Visited.insert(U))
-          Worklist.push_back(U);
-      }
+      for (Use &UU : I->uses())
+        if (Visited.insert(&UU).second)
+          Worklist.push_back(&UU);
       break;
 
     case Instruction::Call:
     case Instruction::Invoke: {
+      bool Captures = true;
+
+      if (I->getType()->isVoidTy())
+        Captures = false;
+
+      auto AddUsersToWorklistIfCapturing = [&] {
+        if (Captures)
+          for (Use &UU : I->uses())
+            if (Visited.insert(&UU).second)
+              Worklist.push_back(&UU);
+      };
+
       CallSite CS(I);
-      if (CS.doesNotAccessMemory())
+      if (CS.doesNotAccessMemory()) {
+        AddUsersToWorklistIfCapturing();
         continue;
+      }
 
       Function *F = CS.getCalledFunction();
       if (!F) {
         if (CS.onlyReadsMemory()) {
           IsRead = true;
+          AddUsersToWorklistIfCapturing();
           continue;
         }
         return Attribute::None;
@@ -475,6 +442,7 @@ determinePointerReadAttrs(Argument *A,
                    "More params than args in non-varargs call.");
             return Attribute::None;
           }
+          Captures &= !CS.doesNotCapture(A - B);
           if (SCCNodes.count(AI))
             continue;
           if (!CS.onlyReadsMemory() && !CS.onlyReadsMemory(A - B))
@@ -483,6 +451,7 @@ determinePointerReadAttrs(Argument *A,
             IsRead = true;
         }
       }
+      AddUsersToWorklistIfCapturing();
       break;
     }
 
@@ -502,17 +471,18 @@ determinePointerReadAttrs(Argument *A,
   return IsRead ? Attribute::ReadOnly : Attribute::ReadNone;
 }
 
-/// AddArgumentAttrs - Deduce nocapture attributes for the SCC.
+/// Deduce nocapture attributes for the SCC.
 bool FunctionAttrs::AddArgumentAttrs(const CallGraphSCC &SCC) {
   bool Changed = false;
 
-  SmallPtrSet<Function*, 8> SCCNodes;
+  SmallPtrSet<Function *, 8> SCCNodes;
 
   // Fill SCCNodes with the elements of the SCC.  Used for quickly
   // looking up whether a given CallGraphNode is in this SCC.
   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
     Function *F = (*I)->getFunction();
-    if (F && !F->isDeclaration() && !F->mayBeOverridden())
+    if (F && !F->isDeclaration() && !F->mayBeOverridden() &&
+        !F->hasFnAttribute(Attribute::OptimizeNone))
       SCCNodes.insert(F);
   }
 
@@ -526,8 +496,9 @@ bool FunctionAttrs::AddArgumentAttrs(const CallGraphSCC &SCC) {
   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
     Function *F = (*I)->getFunction();
 
-    if (F == 0)
-      // External node - only a problem for arguments that we pass to it.
+    if (!F || F->hasFnAttribute(Attribute::OptimizeNone))
+      // External node or function we're trying not to optimize - only a problem
+      // for arguments that we pass to it.
       continue;
 
     // Definitions with weak linkage may be overridden at linktime with
@@ -539,8 +510,8 @@ bool FunctionAttrs::AddArgumentAttrs(const CallGraphSCC &SCC) {
     // a value can't capture arguments. Don't analyze them.
     if (F->onlyReadsMemory() && F->doesNotThrow() &&
         F->getReturnType()->isVoidTy()) {
-      for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end();
-           A != E; ++A) {
+      for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
+           ++A) {
         if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) {
           A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo() + 1, B));
           ++NumNoCapture;
@@ -550,9 +521,10 @@ bool FunctionAttrs::AddArgumentAttrs(const CallGraphSCC &SCC) {
       continue;
     }
 
-    for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end();
-         A != E; ++A) {
-      if (!A->getType()->isPointerTy()) continue;
+    for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
+         ++A) {
+      if (!A->getType()->isPointerTy())
+        continue;
       bool HasNonLocalUses = false;
       if (!A->hasNoCaptureAttr()) {
         ArgumentUsesTracker Tracker(SCCNodes);
@@ -560,7 +532,8 @@ bool FunctionAttrs::AddArgumentAttrs(const CallGraphSCC &SCC) {
         if (!Tracker.Captured) {
           if (Tracker.Uses.empty()) {
             // If it's trivially not captured, mark it nocapture now.
-            A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo()+1, B));
+            A->addAttr(
+                AttributeSet::get(F->getContext(), A->getArgNo() + 1, B));
             ++NumNoCapture;
             Changed = true;
           } else {
@@ -568,8 +541,10 @@ bool FunctionAttrs::AddArgumentAttrs(const CallGraphSCC &SCC) {
             // then it must be calling into another function in our SCC. Save
             // its particulars for Argument-SCC analysis later.
             ArgumentGraphNode *Node = AG[A];
-            for (SmallVectorImpl<Argument*>::iterator UI = Tracker.Uses.begin(),
-                     UE = Tracker.Uses.end(); UI != UE; ++UI) {
+            for (SmallVectorImpl<Argument *>::iterator
+                     UI = Tracker.Uses.begin(),
+                     UE = Tracker.Uses.end();
+                 UI != UE; ++UI) {
               Node->Uses.push_back(AG[*UI]);
               if (*UI != A)
                 HasNonLocalUses = true;
@@ -583,7 +558,7 @@ bool FunctionAttrs::AddArgumentAttrs(const CallGraphSCC &SCC) {
         // Note that we don't allow any calls at all here, or else our result
         // will be dependent on the iteration order through the functions in the
         // SCC.
-        SmallPtrSet<Argument*, 8> Self;
+        SmallPtrSet<Argument *, 8> Self;
         Self.insert(A);
         Attribute::AttrKind R = determinePointerReadAttrs(A, Self);
         if (R != Attribute::None) {
@@ -604,10 +579,11 @@ bool FunctionAttrs::AddArgumentAttrs(const CallGraphSCC &SCC) {
   // made.  If the definition doesn't have a 'nocapture' attribute by now, it
   // captures.
 
-  for (scc_iterator<ArgumentGraph*> I = scc_begin(&AG); !I.isAtEnd(); ++I) {
-    std::vector<ArgumentGraphNode*> &ArgumentSCC = *I;
+  for (scc_iterator<ArgumentGraph *> I = scc_begin(&AG); !I.isAtEnd(); ++I) {
+    const std::vector<ArgumentGraphNode *> &ArgumentSCC = *I;
     if (ArgumentSCC.size() == 1) {
-      if (!ArgumentSCC[0]->Definition) continue;  // synthetic root node
+      if (!ArgumentSCC[0]->Definition)
+        continue; // synthetic root node
 
       // eg. "void f(int* x) { if (...) f(x); }"
       if (ArgumentSCC[0]->Uses.size() == 1 &&
@@ -621,29 +597,30 @@ bool FunctionAttrs::AddArgumentAttrs(const CallGraphSCC &SCC) {
     }
 
     bool SCCCaptured = false;
-    for (std::vector<ArgumentGraphNode*>::iterator I = ArgumentSCC.begin(),
-           E = ArgumentSCC.end(); I != E && !SCCCaptured; ++I) {
+    for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
+         I != E && !SCCCaptured; ++I) {
       ArgumentGraphNode *Node = *I;
       if (Node->Uses.empty()) {
         if (!Node->Definition->hasNoCaptureAttr())
           SCCCaptured = true;
       }
     }
-    if (SCCCaptured) continue;
+    if (SCCCaptured)
+      continue;
 
-    SmallPtrSet<Argument*, 8> ArgumentSCCNodes;
+    SmallPtrSet<Argument *, 8> ArgumentSCCNodes;
     // Fill ArgumentSCCNodes with the elements of the ArgumentSCC.  Used for
     // quickly looking up whether a given Argument is in this ArgumentSCC.
-    for (std::vector<ArgumentGraphNode*>::iterator I = ArgumentSCC.begin(),
-           E = ArgumentSCC.end(); I != E; ++I) {
+    for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end(); I != E; ++I) {
       ArgumentSCCNodes.insert((*I)->Definition);
     }
 
-    for (std::vector<ArgumentGraphNode*>::iterator I = ArgumentSCC.begin(),
-           E = ArgumentSCC.end(); I != E && !SCCCaptured; ++I) {
+    for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
+         I != E && !SCCCaptured; ++I) {
       ArgumentGraphNode *N = *I;
-      for (SmallVectorImpl<ArgumentGraphNode*>::iterator UI = N->Uses.begin(),
-             UE = N->Uses.end(); UI != UE; ++UI) {
+      for (SmallVectorImpl<ArgumentGraphNode *>::iterator UI = N->Uses.begin(),
+                                                          UE = N->Uses.end();
+           UI != UE; ++UI) {
         Argument *A = (*UI)->Definition;
         if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A))
           continue;
@@ -651,7 +628,8 @@ bool FunctionAttrs::AddArgumentAttrs(const CallGraphSCC &SCC) {
         break;
       }
     }
-    if (SCCCaptured) continue;
+    if (SCCCaptured)
+      continue;
 
     for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
       Argument *A = ArgumentSCC[i]->Definition;
@@ -686,10 +664,13 @@ bool FunctionAttrs::AddArgumentAttrs(const CallGraphSCC &SCC) {
     }
 
     if (ReadAttr != Attribute::None) {
-      AttrBuilder B;
+      AttrBuilder B, R;
       B.addAttribute(ReadAttr);
+      R.addAttribute(Attribute::ReadOnly).addAttribute(Attribute::ReadNone);
       for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
         Argument *A = ArgumentSCC[i]->Definition;
+        // Clear out existing readonly/readnone attributes
+        A->removeAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, R));
         A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B));
         ReadAttr == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
         Changed = true;
@@ -700,10 +681,12 @@ bool FunctionAttrs::AddArgumentAttrs(const CallGraphSCC &SCC) {
   return Changed;
 }
 
-/// IsFunctionMallocLike - A function is malloc-like if it returns either null
-/// or a pointer that doesn't alias any other pointer visible to the caller.
-bool FunctionAttrs::IsFunctionMallocLike(Function *F,
-                              SmallPtrSet<Function*, 8> &SCCNodes) const {
+/// Tests whether a function is "malloc-like".
+///
+/// A function is "malloc-like" if it returns either null or a pointer that
+/// doesn't alias any other pointer visible to the caller.
+bool FunctionAttrs::IsFunctionMallocLike(
+    Function *F, SmallPtrSet<Function *, 8> &SCCNodes) const {
   SmallSetVector<Value *, 8> FlowsToReturn;
   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
     if (ReturnInst *Ret = dyn_cast<ReturnInst>(I->getTerminator()))
@@ -724,39 +707,38 @@ bool FunctionAttrs::IsFunctionMallocLike(Function *F,
 
     if (Instruction *RVI = dyn_cast<Instruction>(RetVal))
       switch (RVI->getOpcode()) {
-        // Extend the analysis by looking upwards.
-        case Instruction::BitCast:
-        case Instruction::GetElementPtr:
-        case Instruction::AddrSpaceCast:
-          FlowsToReturn.insert(RVI->getOperand(0));
-          continue;
-        case Instruction::Select: {
-          SelectInst *SI = cast<SelectInst>(RVI);
-          FlowsToReturn.insert(SI->getTrueValue());
-          FlowsToReturn.insert(SI->getFalseValue());
-          continue;
-        }
-        case Instruction::PHI: {
-          PHINode *PN = cast<PHINode>(RVI);
-          for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
-            FlowsToReturn.insert(PN->getIncomingValue(i));
-          continue;
-        }
+      // Extend the analysis by looking upwards.
+      case Instruction::BitCast:
+      case Instruction::GetElementPtr:
+      case Instruction::AddrSpaceCast:
+        FlowsToReturn.insert(RVI->getOperand(0));
+        continue;
+      case Instruction::Select: {
+        SelectInst *SI = cast<SelectInst>(RVI);
+        FlowsToReturn.insert(SI->getTrueValue());
+        FlowsToReturn.insert(SI->getFalseValue());
+        continue;
+      }
+      case Instruction::PHI: {
+        PHINode *PN = cast<PHINode>(RVI);
+        for (Value *IncValue : PN->incoming_values())
+          FlowsToReturn.insert(IncValue);
+        continue;
+      }
 
-        // Check whether the pointer came from an allocation.
-        case Instruction::Alloca:
+      // Check whether the pointer came from an allocation.
+      case Instruction::Alloca:
+        break;
+      case Instruction::Call:
+      case Instruction::Invoke: {
+        CallSite CS(RVI);
+        if (CS.paramHasAttr(0, Attribute::NoAlias))
           break;
-        case Instruction::Call:
-        case Instruction::Invoke: {
-          CallSite CS(RVI);
-          if (CS.paramHasAttr(0, Attribute::NoAlias))
-            break;
-          if (CS.getCalledFunction() &&
-              SCCNodes.count(CS.getCalledFunction()))
-            break;
-        } // fall-through
-        default:
-          return false;  // Did not come from an allocation.
+        if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction()))
+          break;
+      } // fall-through
+      default:
+        return false; // Did not come from an allocation.
       }
 
     if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false))
@@ -766,9 +748,9 @@ bool FunctionAttrs::IsFunctionMallocLike(Function *F,
   return true;
 }
 
-/// AddNoAliasAttrs - Deduce noalias attributes for the SCC.
+/// Deduce noalias attributes for the SCC.
 bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC &SCC) {
-  SmallPtrSet<Function*, 8> SCCNodes;
+  SmallPtrSet<Function *, 8> SCCNodes;
 
   // Fill SCCNodes with the elements of the SCC.  Used for quickly
   // looking up whether a given CallGraphNode is in this SCC.
@@ -780,8 +762,8 @@ bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC &SCC) {
   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
     Function *F = (*I)->getFunction();
 
-    if (F == 0)
-      // External node - skip it;
+    if (!F || F->hasFnAttribute(Attribute::OptimizeNone))
+      // External node or node we don't want to optimize - skip it;
       return false;
 
     // Already noalias.
@@ -793,7 +775,7 @@ bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC &SCC) {
     if (F->isDeclaration() || F->mayBeOverridden())
       return false;
 
-    // We annotate noalias return values, which are only applicable to 
+    // We annotate noalias return values, which are only applicable to
     // pointer types.
     if (!F->getReturnType()->isPointerTy())
       continue;
@@ -816,10 +798,195 @@ bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC &SCC) {
   return MadeChange;
 }
 
-/// inferPrototypeAttributes - Analyze the name and prototype of the
-/// given function and set any applicable attributes.  Returns true
-/// if any attributes were set and false otherwise.
+/// Tests whether this function is known to not return null.
+bool FunctionAttrs::ReturnsNonNull(Function *F,
+                                   SmallPtrSet<Function *, 8> &SCCNodes,
+                                   bool &Speculative) const {
+  assert(F->getReturnType()->isPointerTy() &&
+         "nonnull only meaningful on pointer types");
+  Speculative = false;
+
+  SmallSetVector<Value *, 8> FlowsToReturn;
+  for (BasicBlock &BB : *F)
+    if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator()))
+      FlowsToReturn.insert(Ret->getReturnValue());
+
+  for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
+    Value *RetVal = FlowsToReturn[i];
+
+    // If this value is locally known to be non-null, we're good
+    if (isKnownNonNull(RetVal, TLI))
+      continue;
+
+    // Otherwise, we need to look upwards since we can't make any local
+    // conclusions.
+    Instruction *RVI = dyn_cast<Instruction>(RetVal);
+    if (!RVI)
+      return false;
+    switch (RVI->getOpcode()) {
+    // Extend the analysis by looking upwards.
+    case Instruction::BitCast:
+    case Instruction::GetElementPtr:
+    case Instruction::AddrSpaceCast:
+      FlowsToReturn.insert(RVI->getOperand(0));
+      continue;
+    case Instruction::Select: {
+      SelectInst *SI = cast<SelectInst>(RVI);
+      FlowsToReturn.insert(SI->getTrueValue());
+      FlowsToReturn.insert(SI->getFalseValue());
+      continue;
+    }
+    case Instruction::PHI: {
+      PHINode *PN = cast<PHINode>(RVI);
+      for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
+        FlowsToReturn.insert(PN->getIncomingValue(i));
+      continue;
+    }
+    case Instruction::Call:
+    case Instruction::Invoke: {
+      CallSite CS(RVI);
+      Function *Callee = CS.getCalledFunction();
+      // A call to a node within the SCC is assumed to return null until
+      // proven otherwise
+      if (Callee && SCCNodes.count(Callee)) {
+        Speculative = true;
+        continue;
+      }
+      return false;
+    }
+    default:
+      return false; // Unknown source, may be null
+    };
+    llvm_unreachable("should have either continued or returned");
+  }
+
+  return true;
+}
+
+/// Deduce nonnull attributes for the SCC.
+bool FunctionAttrs::AddNonNullAttrs(const CallGraphSCC &SCC) {
+  SmallPtrSet<Function *, 8> SCCNodes;
+
+  // Fill SCCNodes with the elements of the SCC.  Used for quickly
+  // looking up whether a given CallGraphNode is in this SCC.
+  for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I)
+    SCCNodes.insert((*I)->getFunction());
+
+  // Speculative that all functions in the SCC return only nonnull
+  // pointers.  We may refute this as we analyze functions.
+  bool SCCReturnsNonNull = true;
+
+  bool MadeChange = false;
+
+  // Check each function in turn, determining which functions return nonnull
+  // pointers.
+  for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
+    Function *F = (*I)->getFunction();
+
+    if (!F || F->hasFnAttribute(Attribute::OptimizeNone))
+      // External node or node we don't want to optimize - skip it;
+      return false;
+
+    // Already nonnull.
+    if (F->getAttributes().hasAttribute(AttributeSet::ReturnIndex,
+                                        Attribute::NonNull))
+      continue;
+
+    // Definitions with weak linkage may be overridden at linktime, so
+    // treat them like declarations.
+    if (F->isDeclaration() || F->mayBeOverridden())
+      return false;
+
+    // We annotate nonnull return values, which are only applicable to
+    // pointer types.
+    if (!F->getReturnType()->isPointerTy())
+      continue;
+
+    bool Speculative = false;
+    if (ReturnsNonNull(F, SCCNodes, Speculative)) {
+      if (!Speculative) {
+        // Mark the function eagerly since we may discover a function
+        // which prevents us from speculating about the entire SCC
+        DEBUG(dbgs() << "Eagerly marking " << F->getName() << " as nonnull\n");
+        F->addAttribute(AttributeSet::ReturnIndex, Attribute::NonNull);
+        ++NumNonNullReturn;
+        MadeChange = true;
+      }
+      continue;
+    }
+    // At least one function returns something which could be null, can't
+    // speculate any more.
+    SCCReturnsNonNull = false;
+  }
+
+  if (SCCReturnsNonNull) {
+    for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
+      Function *F = (*I)->getFunction();
+      if (F->getAttributes().hasAttribute(AttributeSet::ReturnIndex,
+                                          Attribute::NonNull) ||
+          !F->getReturnType()->isPointerTy())
+        continue;
+
+      DEBUG(dbgs() << "SCC marking " << F->getName() << " as nonnull\n");
+      F->addAttribute(AttributeSet::ReturnIndex, Attribute::NonNull);
+      ++NumNonNullReturn;
+      MadeChange = true;
+    }
+  }
+
+  return MadeChange;
+}
+
+static void setDoesNotAccessMemory(Function &F) {
+  if (!F.doesNotAccessMemory()) {
+    F.setDoesNotAccessMemory();
+    ++NumAnnotated;
+  }
+}
+
+static void setOnlyReadsMemory(Function &F) {
+  if (!F.onlyReadsMemory()) {
+    F.setOnlyReadsMemory();
+    ++NumAnnotated;
+  }
+}
+
+static void setDoesNotThrow(Function &F) {
+  if (!F.doesNotThrow()) {
+    F.setDoesNotThrow();
+    ++NumAnnotated;
+  }
+}
+
+static void setDoesNotCapture(Function &F, unsigned n) {
+  if (!F.doesNotCapture(n)) {
+    F.setDoesNotCapture(n);
+    ++NumAnnotated;
+  }
+}
+
+static void setOnlyReadsMemory(Function &F, unsigned n) {
+  if (!F.onlyReadsMemory(n)) {
+    F.setOnlyReadsMemory(n);
+    ++NumAnnotated;
+  }
+}
+
+static void setDoesNotAlias(Function &F, unsigned n) {
+  if (!F.doesNotAlias(n)) {
+    F.setDoesNotAlias(n);
+    ++NumAnnotated;
+  }
+}
+
+/// Analyze the name and prototype of the given function and set any applicable
+/// attributes.
+///
+/// Returns true if any attributes were set and false otherwise.
 bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
+  if (F.hasFnAttribute(Attribute::OptimizeNone))
+    return false;
+
   FunctionType *FTy = F.getFunctionType();
   LibFunc::Func TheLibFunc;
   if (!(TLI->getLibFunc(F.getName(), TheLibFunc) && TLI->has(TheLibFunc)))
@@ -835,8 +1002,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     break;
   case LibFunc::strchr:
   case LibFunc::strrchr:
-    if (FTy->getNumParams() != 2 ||
-        !FTy->getParamType(0)->isPointerTy() ||
+    if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getParamType(1)->isIntegerTy())
       return false;
     setOnlyReadsMemory(F);
@@ -849,8 +1015,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
   case LibFunc::strtoll:
   case LibFunc::strtold:
   case LibFunc::strtoull:
-    if (FTy->getNumParams() < 2 ||
-        !FTy->getParamType(1)->isPointerTy())
+    if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy())
       return false;
     setDoesNotThrow(F);
     setDoesNotCapture(F, 2);
@@ -862,16 +1027,14 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
   case LibFunc::strncat:
   case LibFunc::strncpy:
   case LibFunc::stpncpy:
-    if (FTy->getNumParams() < 2 ||
-        !FTy->getParamType(1)->isPointerTy())
+    if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy())
       return false;
     setDoesNotThrow(F);
     setDoesNotCapture(F, 2);
     setOnlyReadsMemory(F, 2);
     break;
   case LibFunc::strxfrm:
-    if (FTy->getNumParams() != 3 ||
-        !FTy->getParamType(0)->isPointerTy() ||
+    if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getParamType(1)->isPointerTy())
       return false;
     setDoesNotThrow(F);
@@ -879,15 +1042,14 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setDoesNotCapture(F, 2);
     setOnlyReadsMemory(F, 2);
     break;
-  case LibFunc::strcmp: //0,1
-    case LibFunc::strspn: // 0,1
-    case LibFunc::strncmp: // 0,1
-    case LibFunc::strcspn: //0,1
-    case LibFunc::strcoll: //0,1
-    case LibFunc::strcasecmp:  // 0,1
-    case LibFunc::strncasecmp: // 
-    if (FTy->getNumParams() < 2 ||
-        !FTy->getParamType(0)->isPointerTy() ||
+  case LibFunc::strcmp: // 0,1
+  case LibFunc::strspn:  // 0,1
+  case LibFunc::strncmp: // 0,1
+  case LibFunc::strcspn: // 0,1
+  case LibFunc::strcoll: // 0,1
+  case LibFunc::strcasecmp:  // 0,1
+  case LibFunc::strncasecmp: //
+    if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getParamType(1)->isPointerTy())
       return false;
     setOnlyReadsMemory(F);
@@ -937,8 +1099,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     break;
   case LibFunc::stat:
   case LibFunc::statvfs:
-    if (FTy->getNumParams() < 2 ||
-        !FTy->getParamType(0)->isPointerTy() ||
+    if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getParamType(1)->isPointerTy())
       return false;
     setDoesNotThrow(F);
@@ -947,8 +1108,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setOnlyReadsMemory(F, 1);
     break;
   case LibFunc::sscanf:
-    if (FTy->getNumParams() < 2 ||
-        !FTy->getParamType(0)->isPointerTy() ||
+    if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getParamType(1)->isPointerTy())
       return false;
     setDoesNotThrow(F);
@@ -958,8 +1118,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setOnlyReadsMemory(F, 2);
     break;
   case LibFunc::sprintf:
-    if (FTy->getNumParams() < 2 ||
-        !FTy->getParamType(0)->isPointerTy() ||
+    if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getParamType(1)->isPointerTy())
       return false;
     setDoesNotThrow(F);
@@ -968,8 +1127,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setOnlyReadsMemory(F, 2);
     break;
   case LibFunc::snprintf:
-    if (FTy->getNumParams() != 3 ||
-        !FTy->getParamType(0)->isPointerTy() ||
+    if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getParamType(2)->isPointerTy())
       return false;
     setDoesNotThrow(F);
@@ -978,8 +1136,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setOnlyReadsMemory(F, 3);
     break;
   case LibFunc::setitimer:
-    if (FTy->getNumParams() != 3 ||
-        !FTy->getParamType(1)->isPointerTy() ||
+    if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy() ||
         !FTy->getParamType(2)->isPointerTy())
       return false;
     setDoesNotThrow(F);
@@ -988,23 +1145,20 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setOnlyReadsMemory(F, 2);
     break;
   case LibFunc::system:
-    if (FTy->getNumParams() != 1 ||
-        !FTy->getParamType(0)->isPointerTy())
+    if (FTy->getNumParams() != 1 || !FTy->getParamType(0)->isPointerTy())
       return false;
     // May throw; "system" is a valid pthread cancellation point.
     setDoesNotCapture(F, 1);
     setOnlyReadsMemory(F, 1);
     break;
   case LibFunc::malloc:
-    if (FTy->getNumParams() != 1 ||
-        !FTy->getReturnType()->isPointerTy())
+    if (FTy->getNumParams() != 1 || !FTy->getReturnType()->isPointerTy())
       return false;
     setDoesNotThrow(F);
     setDoesNotAlias(F, 0);
     break;
   case LibFunc::memcmp:
-    if (FTy->getNumParams() != 3 ||
-        !FTy->getParamType(0)->isPointerTy() ||
+    if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getParamType(1)->isPointerTy())
       return false;
     setOnlyReadsMemory(F);
@@ -1022,8 +1176,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
   case LibFunc::modf:
   case LibFunc::modff:
   case LibFunc::modfl:
-    if (FTy->getNumParams() < 2 ||
-        !FTy->getParamType(1)->isPointerTy())
+    if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy())
       return false;
     setDoesNotThrow(F);
     setDoesNotCapture(F, 2);
@@ -1031,8 +1184,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
   case LibFunc::memcpy:
   case LibFunc::memccpy:
   case LibFunc::memmove:
-    if (FTy->getNumParams() < 2 ||
-        !FTy->getParamType(1)->isPointerTy())
+    if (FTy->getNumParams() < 2 || !FTy->getParamType(1)->isPointerTy())
       return false;
     setDoesNotThrow(F);
     setDoesNotCapture(F, 2);
@@ -1044,23 +1196,20 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setDoesNotAlias(F, 0);
     break;
   case LibFunc::mkdir:
-    if (FTy->getNumParams() == 0 ||
-        !FTy->getParamType(0)->isPointerTy())
+    if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
       return false;
     setDoesNotThrow(F);
     setDoesNotCapture(F, 1);
     setOnlyReadsMemory(F, 1);
     break;
   case LibFunc::mktime:
-    if (FTy->getNumParams() == 0 ||
-        !FTy->getParamType(0)->isPointerTy())
+    if (FTy->getNumParams() == 0 || !FTy->getParamType(0)->isPointerTy())
       return false;
     setDoesNotThrow(F);
     setDoesNotCapture(F, 1);
     break;
   case LibFunc::realloc:
-    if (FTy->getNumParams() != 2 ||
-        !FTy->getParamType(0)->isPointerTy() ||
+    if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getReturnType()->isPointerTy())
       return false;
     setDoesNotThrow(F);
@@ -1068,15 +1217,13 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setDoesNotCapture(F, 1);
     break;
   case LibFunc::read:
-    if (FTy->getNumParams() != 3 ||
-        !FTy->getParamType(1)->isPointerTy())
+    if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy())
       return false;
     // May throw; "read" is a valid pthread cancellation point.
     setDoesNotCapture(F, 2);
     break;
   case LibFunc::rewind:
-    if (FTy->getNumParams() < 1 ||
-        !FTy->getParamType(0)->isPointerTy())
+    if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
       return false;
     setDoesNotThrow(F);
     setDoesNotCapture(F, 1);
@@ -1084,16 +1231,14 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
   case LibFunc::rmdir:
   case LibFunc::remove:
   case LibFunc::realpath:
-    if (FTy->getNumParams() < 1 ||
-        !FTy->getParamType(0)->isPointerTy())
+    if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
       return false;
     setDoesNotThrow(F);
     setDoesNotCapture(F, 1);
     setOnlyReadsMemory(F, 1);
     break;
   case LibFunc::rename:
-    if (FTy->getNumParams() < 2 ||
-        !FTy->getParamType(0)->isPointerTy() ||
+    if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getParamType(1)->isPointerTy())
       return false;
     setDoesNotThrow(F);
@@ -1103,8 +1248,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setOnlyReadsMemory(F, 2);
     break;
   case LibFunc::readlink:
-    if (FTy->getNumParams() < 2 ||
-        !FTy->getParamType(0)->isPointerTy() ||
+    if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getParamType(1)->isPointerTy())
       return false;
     setDoesNotThrow(F);
@@ -1120,8 +1264,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setOnlyReadsMemory(F, 2);
     break;
   case LibFunc::bcopy:
-    if (FTy->getNumParams() != 3 ||
-        !FTy->getParamType(0)->isPointerTy() ||
+    if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getParamType(1)->isPointerTy())
       return false;
     setDoesNotThrow(F);
@@ -1130,8 +1273,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setOnlyReadsMemory(F, 1);
     break;
   case LibFunc::bcmp:
-    if (FTy->getNumParams() != 3 ||
-        !FTy->getParamType(0)->isPointerTy() ||
+    if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getParamType(1)->isPointerTy())
       return false;
     setDoesNotThrow(F);
@@ -1146,8 +1288,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setDoesNotCapture(F, 1);
     break;
   case LibFunc::calloc:
-    if (FTy->getNumParams() != 2 ||
-        !FTy->getReturnType()->isPointerTy())
+    if (FTy->getNumParams() != 2 || !FTy->getReturnType()->isPointerTy())
       return false;
     setDoesNotThrow(F);
     setDoesNotAlias(F, 0);
@@ -1186,8 +1327,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setOnlyReadsMemory(F, 1);
     break;
   case LibFunc::fopen:
-    if (FTy->getNumParams() != 2 ||
-        !FTy->getReturnType()->isPointerTy() ||
+    if (FTy->getNumParams() != 2 || !FTy->getReturnType()->isPointerTy() ||
         !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getParamType(1)->isPointerTy())
       return false;
@@ -1199,8 +1339,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setOnlyReadsMemory(F, 2);
     break;
   case LibFunc::fdopen:
-    if (FTy->getNumParams() != 2 ||
-        !FTy->getReturnType()->isPointerTy() ||
+    if (FTy->getNumParams() != 2 || !FTy->getReturnType()->isPointerTy() ||
         !FTy->getParamType(1)->isPointerTy())
       return false;
     setDoesNotThrow(F);
@@ -1246,16 +1385,14 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setDoesNotCapture(F, 2);
     break;
   case LibFunc::fgets:
-    if (FTy->getNumParams() != 3 ||
-        !FTy->getParamType(0)->isPointerTy() ||
+    if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getParamType(2)->isPointerTy())
       return false;
     setDoesNotThrow(F);
     setDoesNotCapture(F, 3);
     break;
   case LibFunc::fread:
-    if (FTy->getNumParams() != 4 ||
-        !FTy->getParamType(0)->isPointerTy() ||
+    if (FTy->getNumParams() != 4 || !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getParamType(3)->isPointerTy())
       return false;
     setDoesNotThrow(F);
@@ -1263,8 +1400,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setDoesNotCapture(F, 4);
     break;
   case LibFunc::fwrite:
-    if (FTy->getNumParams() != 4 ||
-        !FTy->getParamType(0)->isPointerTy() ||
+    if (FTy->getNumParams() != 4 || !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getParamType(3)->isPointerTy())
       return false;
     setDoesNotThrow(F);
@@ -1272,8 +1408,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setDoesNotCapture(F, 4);
     break;
   case LibFunc::fputs:
-    if (FTy->getNumParams() < 2 ||
-        !FTy->getParamType(0)->isPointerTy() ||
+    if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getParamType(1)->isPointerTy())
       return false;
     setDoesNotThrow(F);
@@ -1283,8 +1418,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     break;
   case LibFunc::fscanf:
   case LibFunc::fprintf:
-    if (FTy->getNumParams() < 2 ||
-        !FTy->getParamType(0)->isPointerTy() ||
+    if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getParamType(1)->isPointerTy())
       return false;
     setDoesNotThrow(F);
@@ -1293,8 +1427,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setOnlyReadsMemory(F, 2);
     break;
   case LibFunc::fgetpos:
-    if (FTy->getNumParams() < 2 ||
-        !FTy->getParamType(0)->isPointerTy() ||
+    if (FTy->getNumParams() < 2 || !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getParamType(1)->isPointerTy())
       return false;
     setDoesNotThrow(F);
@@ -1361,8 +1494,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     break;
   case LibFunc::utime:
   case LibFunc::utimes:
-    if (FTy->getNumParams() != 2 ||
-        !FTy->getParamType(0)->isPointerTy() ||
+    if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getParamType(1)->isPointerTy())
       return false;
     setDoesNotThrow(F);
@@ -1403,8 +1535,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setDoesNotThrow(F);
     break;
   case LibFunc::popen:
-    if (FTy->getNumParams() != 2 ||
-        !FTy->getReturnType()->isPointerTy() ||
+    if (FTy->getNumParams() != 2 || !FTy->getReturnType()->isPointerTy() ||
         !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getParamType(1)->isPointerTy())
       return false;
@@ -1429,8 +1560,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setOnlyReadsMemory(F, 1);
     break;
   case LibFunc::vsscanf:
-    if (FTy->getNumParams() != 3 ||
-        !FTy->getParamType(1)->isPointerTy() ||
+    if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy() ||
         !FTy->getParamType(2)->isPointerTy())
       return false;
     setDoesNotThrow(F);
@@ -1440,8 +1570,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setOnlyReadsMemory(F, 2);
     break;
   case LibFunc::vfscanf:
-    if (FTy->getNumParams() != 3 ||
-        !FTy->getParamType(1)->isPointerTy() ||
+    if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy() ||
         !FTy->getParamType(2)->isPointerTy())
       return false;
     setDoesNotThrow(F);
@@ -1464,8 +1593,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     break;
   case LibFunc::vfprintf:
   case LibFunc::vsprintf:
-    if (FTy->getNumParams() != 3 ||
-        !FTy->getParamType(0)->isPointerTy() ||
+    if (FTy->getNumParams() != 3 || !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getParamType(1)->isPointerTy())
       return false;
     setDoesNotThrow(F);
@@ -1474,8 +1602,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setOnlyReadsMemory(F, 2);
     break;
   case LibFunc::vsnprintf:
-    if (FTy->getNumParams() != 4 ||
-        !FTy->getParamType(0)->isPointerTy() ||
+    if (FTy->getNumParams() != 4 || !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getParamType(2)->isPointerTy())
       return false;
     setDoesNotThrow(F);
@@ -1491,8 +1618,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setOnlyReadsMemory(F, 1);
     break;
   case LibFunc::opendir:
-    if (FTy->getNumParams() != 1 ||
-        !FTy->getReturnType()->isPointerTy() ||
+    if (FTy->getNumParams() != 1 || !FTy->getReturnType()->isPointerTy() ||
         !FTy->getParamType(0)->isPointerTy())
       return false;
     setDoesNotThrow(F);
@@ -1520,8 +1646,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setDoesNotAccessMemory(F);
     break;
   case LibFunc::lstat:
-    if (FTy->getNumParams() != 2 ||
-        !FTy->getParamType(0)->isPointerTy() ||
+    if (FTy->getNumParams() != 2 || !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getParamType(1)->isPointerTy())
       return false;
     setDoesNotThrow(F);
@@ -1544,8 +1669,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     break;
   case LibFunc::dunder_strdup:
   case LibFunc::dunder_strndup:
-    if (FTy->getNumParams() < 1 ||
-        !FTy->getReturnType()->isPointerTy() ||
+    if (FTy->getNumParams() < 1 || !FTy->getReturnType()->isPointerTy() ||
         !FTy->getParamType(0)->isPointerTy())
       return false;
     setDoesNotThrow(F);
@@ -1554,8 +1678,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setOnlyReadsMemory(F, 1);
     break;
   case LibFunc::dunder_strtok_r:
-    if (FTy->getNumParams() != 3 ||
-        !FTy->getParamType(1)->isPointerTy())
+    if (FTy->getNumParams() != 3 || !FTy->getParamType(1)->isPointerTy())
       return false;
     setDoesNotThrow(F);
     setDoesNotCapture(F, 2);
@@ -1574,8 +1697,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setDoesNotCapture(F, 2);
     break;
   case LibFunc::dunder_isoc99_scanf:
-    if (FTy->getNumParams() < 1 ||
-        !FTy->getParamType(0)->isPointerTy())
+    if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy())
       return false;
     setDoesNotThrow(F);
     setDoesNotCapture(F, 1);
@@ -1584,8 +1706,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
   case LibFunc::stat64:
   case LibFunc::lstat64:
   case LibFunc::statvfs64:
-    if (FTy->getNumParams() < 1 ||
-        !FTy->getParamType(0)->isPointerTy() ||
+    if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getParamType(1)->isPointerTy())
       return false;
     setDoesNotThrow(F);
@@ -1594,8 +1715,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setOnlyReadsMemory(F, 1);
     break;
   case LibFunc::dunder_isoc99_sscanf:
-    if (FTy->getNumParams() < 1 ||
-        !FTy->getParamType(0)->isPointerTy() ||
+    if (FTy->getNumParams() < 1 || !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getParamType(1)->isPointerTy())
       return false;
     setDoesNotThrow(F);
@@ -1605,8 +1725,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setOnlyReadsMemory(F, 2);
     break;
   case LibFunc::fopen64:
-    if (FTy->getNumParams() != 2 ||
-        !FTy->getReturnType()->isPointerTy() ||
+    if (FTy->getNumParams() != 2 || !FTy->getReturnType()->isPointerTy() ||
         !FTy->getParamType(0)->isPointerTy() ||
         !FTy->getParamType(1)->isPointerTy())
       return false;
@@ -1654,6 +1773,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
     setDoesNotThrow(F);
     setDoesNotCapture(F, 1);
     setDoesNotCapture(F, 2);
+    break;
   default:
     // Didn't mark any attributes.
     return false;
@@ -1662,8 +1782,7 @@ bool FunctionAttrs::inferPrototypeAttributes(Function &F) {
   return true;
 }
 
-/// annotateLibraryCalls - Adds attributes to well-known standard library
-/// call declarations.
+/// Adds attributes to well-known standard library call declarations.
 bool FunctionAttrs::annotateLibraryCalls(const CallGraphSCC &SCC) {
   bool MadeChange = false;
 
@@ -1672,7 +1791,7 @@ bool FunctionAttrs::annotateLibraryCalls(const CallGraphSCC &SCC) {
   for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) {
     Function *F = (*I)->getFunction();
 
-    if (F != 0 && F->isDeclaration())
+    if (F && F->isDeclaration())
       MadeChange |= inferPrototypeAttributes(*F);
   }
 
@@ -1680,12 +1799,12 @@ bool FunctionAttrs::annotateLibraryCalls(const CallGraphSCC &SCC) {
 }
 
 bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) {
-  AA = &getAnalysis<AliasAnalysis>();
-  TLI = &getAnalysis<TargetLibraryInfo>();
+  TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
 
   bool Changed = annotateLibraryCalls(SCC);
   Changed |= AddReadAttrs(SCC);
   Changed |= AddArgumentAttrs(SCC);
   Changed |= AddNoAliasAttrs(SCC);
+  Changed |= AddNonNullAttrs(SCC);
   return Changed;
 }