[WIP] Fixpoint iteration system for IPO attribute deduction

[jdoerfert]

Summary

NOTE: This is a prototype that needs a lot of cleanup but shows how the overall system could look like! The actual code review will happen on smaller chunks of this code, adding one feature at a time, first without removing the existing code path.

In the end, this commit shows how we should replace the current
"inter-procedural function attribute deduction" with a fixpoint
iteration system. For some problems with the current implementation see
[1]. The new system allows to determine various properties, including
inter-procedural function attributes, through interlaced fixpoint
iterations. All "in-flight" attributes can query the optimistic and
known values of other attributes computed in the same fixpoint
iteration. This allows better interference if there is a mutual
dependence. Dedicated fixpoint propagations determine information
alternating through forward and backward deduction (wrt. the execution
flow) until neither yields new results (or we decide to give up).

This prototype implementation:

• determines all attributes we did with the existing code
• adds detection for multiple new attributes
• shows how local information, e.g. dereferenceability due to a load, can be propagated by the system to callees of the function (if applicable) and users of the loaded pointer alike.
• distinguishes six different kinds of attribute "positions", e.g., function attributes and return attributes (see the enum ManifestPosition), five of which can be manifested in IR.

To deduce new attributes, at a known position (see the enum
ManifestPosition), one only needs to inherit from the AbstractAttribute
class and implement all methods without a default implementation. All
but the "bool updateImpl(Attributor &A, Direction Dir)" method are often
one liners.

Comment and remarks welcome!

[1] https://lists.llvm.org/pipermail/llvm-dev/2018-August/125537.html

[jdoerfert]

Cleaned up versions are online now

include/llvm/Transforms/IPO/FunctionAttrs.h

 #define LLVM_TRANSFORMS_IPO_FUNCTIONATTRS_H
 
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
+class AbstractAttribute;
+class DominatorTree;
+class AbstractState;
+class Attributor;
 class AAResults;
+class Statistic;
 class Function;
 class Module;
 class Pass;
 
+namespace {
+
+struct ReturnedValueInfo {
+  ReturnedValueInfo(Value *V = nullptr, Instruction *CtxI = nullptr,
+                    const ReturnedValueInfo *RV = nullptr)
+      : V(V), CtxI(CtxI), RV(RV) {}
+  Value *V;
+  Instruction *CtxI;
+  const ReturnedValueInfo *RV;
+};
+
+template <typename T> using GetterTy = std::function<T &(llvm::Function &)>;
+using AAGetterTy = GetterTy<llvm::AAResults>;
+using DTGetterTy = GetterTy<const llvm::DominatorTree>;
+using SCCNodeSet = llvm::SmallSetVector<llvm::Function *, 8>;
+using AASetVector = llvm::SmallSetVector<AbstractAttribute *, 64>;
+
+template <typename T, typename R = bool> using CallbackTy = std::function<R(T)>;
+using ReturnedValueCallbackTy = CallbackTy<const ReturnedValueInfo *>;
+using InstructionCallbackTy = CallbackTy<Instruction *>;
+using CallSiteCallbackTy = CallbackTy<CallSite>;
+
+template <typename StateTy>
+using ReturnedValueStateCallbackTy =
+    CallbackTy<const ReturnedValueInfo *, StateTy>;
+
+template <typename StateTy>
+using CallSiteStateCallbackTy = CallbackTy<CallSite, StateTy>;
+
+} // anonymous namespace
+
+  enum Direction {
+    FORWARD,
+    BACKWARD,
+  };
+
+/// Base class for all abstract states maintained for potential attributes.
+struct AbstractAttribute {
+
+  enum ManifestPosition {
+    MP_FUNCTION,
+    MP_RETURNED,
+    MP_ARGUMENT,
+    MP_CALL_SITE_ARGUMENT,
+    MP_CALL_SITE_ARGUMENT_NOT_IR,
+    MP_INSTRUCTION_METADATA,
+  };
+
+  /// An abstract attribute for @p V with an optimistic (=bottom) value.
+  AbstractAttribute(Value &V) : V(V) {}
+
+  /// Hook for the Attributor to trigger an update of the internal state.
+  /// If this attribute is already fixed, nothing happens, if it is not, the
+  /// environment was CHANGED and we have to determine if the current
+  /// information is still valid or adjust it otherwise. There is no explicit
+  /// return value but the internal "CHANGED" variable is set accordingly.
+  bool update(Attributor &A, Direction Dir);
+
+  /// Hook for the Attributor to trigger the manifestation of the information
+  /// represented by the abstract attribute in the LLVM-IR.
+  virtual bool manifest(Attributor &A);
+
+  virtual void useKnownAccessInformation(uint64_t Length, const APInt &Offset) {
+    /* No-Op */
+  }
+
+  virtual AbstractState &getState() = 0;
+  virtual const AbstractState &getState() const = 0;
+
+  virtual bool isImplied(Attributor &A, Direction Dir, bool &Changed);
+  virtual bool isImpliedBy(AbstractAttribute &AA, Direction Dir, bool &Changed);
+
+  virtual void registerPrecedingAndSucceedingAAs(const AASetVector &AAs,
+                                                 bool Preceding,
+                                                 bool Succeeding,
+                                                 bool StripInbounds = true);
+
+  /// Return the llvm::Value this abstract attribute is anchored with.
+  /// TODO
+  ///{
+  Value &getAnchoredValue() { return V; }
+  const Value &getAnchoredValue() const { return V; }
+  ///}
+
+  /// Return the llvm::Value this abstract attribute is associated with.
+  ///{
+  virtual Value &getAssociatedValue() { return V; }
+  virtual const Value &getAssociatedValue() const { return V; }
+  ///}
+
+  virtual Statistic *getStatisticObj() const { return nullptr; }
+  virtual ManifestPosition getManifestPosition() const = 0;
+
+  /// Helper functions, for debug purposes only.
+  ///{
+  virtual const std::string getAsStr() const = 0;
+  virtual Attribute::AttrKind getAttrKind() const = 0;
+  virtual uint64_t getAttrValue() const { return 0; };
+  virtual int getArgumentNo() const { return -1; };
+
+  virtual MDNode *getMetadataNode() const {
+    llvm_unreachable("No metadata node available!");
+  };
+  virtual unsigned getMetadataID() const {
+    llvm_unreachable("No metadata ID available!");
+  };
+
+  virtual void print(raw_ostream &OS) const;
+  void dump() const { print(dbgs()); }
+  ///}
+
+  /// The identifier used as a fallback.
+  static constexpr Attribute::AttrKind ID = Attribute::None;
+
+  friend class Attributor;
+
+protected:
+
+  /// The actual update/transfer function which has to be implemented by the
+  /// derived classes.
+  virtual bool updateImpl(Attributor &A, Direction Dir) = 0;
+
+  /// The llvm::Value this abstract attribute is associated with.
+  Value &V;
+
+  AASetVector PrecedingAAs, SucceedingAAs;
+};
+raw_ostream &operator<<(raw_ostream &OS, const AbstractAttribute &AA);
+raw_ostream &operator<<(raw_ostream &OS, AbstractAttribute::ManifestPosition);
+raw_ostream &operator<<(raw_ostream &OS, const AbstractState &State);
+
+
+/// An abstract interface for all non-null attributes.
+struct AANonNull : public AbstractAttribute {
+
+  /// See AbstractAttribute::AbstractAttribute(...).
+  AANonNull(Value &V) : AbstractAttribute(V) {}
+
+  /// Return true if the associated value is known to be non-null.
+  virtual bool isKnownNonNull() const = 0;
+
+  /// Return true if we assume that the underlying value cannot be null. The
+  /// direction @p Dir decides if we look at the assumed information for forward
+  /// or backward traversal, or both, either inclusive or exclusive (see enum
+  /// Direction).
+  virtual bool isAssumedNonNull() const = 0;
+
+  /// See the AbstractAttribute interface for information.
+  ///{
+
+  /// See AbstractState::getAttrKind().
+  Attribute::AttrKind getAttrKind() const override {
+    return ID;
+  }
+
+  /// See AbstractState::getAsStr().
+  virtual const std::string getAsStr() const override {
+    return isAssumedNonNull() ? "non-null" : "maybe-null";
+  }
+
+  ///}
+
+  /// The identifier used by the Attributor for this class of attributes.
+  static constexpr Attribute::AttrKind ID = Attribute::NonNull;
+};
+
+/// An abstract interface for all no-alias attributes.
+struct AANoAlias : public AbstractAttribute {
+
+  /// See AbstractAttribute::AbstractAttribute(...).
+  AANoAlias(Value &V) : AbstractAttribute(V) {}
+
+  /// Return true if we know that the underlying value cannot alias with
+  /// anything (not based on it) in its respective scope.
+  virtual bool isKnownNoAlias() const = 0;
+
+  /// Return true if we assume that the underlying value cannot alias with
+  /// anything (not based on it) in its respective scope. The direction @p Dir
+  /// decides if we look at the assumed information for forward or backward
+  /// traversal, or both, either inclusive or exclusive (see enum Direction).
+  virtual bool isAssumedNoAlias() const = 0;
+
+  /// See the AbstractAttribute interface for information.
+  ///{
+
+  /// See AbstractState::getAttrKind().
+  Attribute::AttrKind getAttrKind() const override {
+    return ID;
+  }
+
+  /// See AbstractState::getAsStr().
+  const std::string getAsStr() const override {
+    return isAssumedNoAlias() ? "no-alias" : "may-alias";
+  };
+
+  ///}
+
+  /// The identifier used by the Attributor for this class of attributes.
+  static constexpr Attribute::AttrKind ID = Attribute::NoAlias;
+};
+
+/// An abstract interface for all nocapture attributes.
+struct AAMemoryAccessBehavior : public AbstractAttribute {
+
+  /// See AbstractAttribute::AbstractAttribute(...).
+  AAMemoryAccessBehavior(Value &V) : AbstractAttribute(V) {}
+
+  /// Return true if we know that the underlying value is not read or accessed
+  /// in its respective scope.
+  virtual bool isKnownReadNone() const = 0;
+
+  /// Return true if we assume that the underlying value is not read or accessed
+  /// in its respective scope.
+  virtual bool isAssumedReadNone() const = 0;
+
+  /// Return true if we know that the underlying value is not accessed
+  /// (=written) in its respective scope.
+  virtual bool isKnownReadOnly() const = 0;
+
+  /// Return true if we assume that the underlying value is not accessed
+  /// (=written) in its respective scope.
+  virtual bool isAssumedReadOnly() const = 0;
+
+  /// Return true if we know that the underlying value is not read in its
+  /// respective scope.
+  virtual bool isKnownWriteOnly() const = 0;
+
+  /// Return true if we assume that the underlying value is not read in its
+  /// respective scope.
+  virtual bool isAssumedWriteOnly() const = 0;
+
+  /// Return true if we know that the underlying value (which has to be a
+  /// function!) will only read argument memory.
+  virtual bool isKnownArgMemOnly() const {
+    llvm_unreachable("isKnownArgMemOnly() is only callable for functions!");
+  }
+
+  /// Return true if we assume that the underlying value (which has to be a
+  /// function!) will only read argument memory.
+  virtual bool isAssumedArgMemOnly() const {
+    llvm_unreachable("isAssumedArgMemOnly() is only callable for functions!");
+  }
+
+  /// See the AbstractAttribute interface for information.
+  ///{
+
+  /// See AbstractState::getAttrKind().
+  Attribute::AttrKind getAttrKind() const override {
+    return isAssumedReadNone()
+               ? Attribute::ReadNone
+               : (isAssumedReadOnly()
+                      ? Attribute::ReadOnly
+                      : (isAssumedWriteOnly() ? Attribute::WriteOnly
+                                              : Attribute::None));
+  }
+
+  /// See AbstractState::getAsStr().
+  const std::string getAsStr() const override {
+    return isAssumedReadNone()
+               ? "readnone"
+               : (isAssumedReadOnly()
+                      ? "readonly"
+                      : (isAssumedWriteOnly() ? "writeonly"
+                                              : "may-read/write"));
+  };
+
+  ///}
+
+  /// The identifier used by the Attributor for this class of attributes.
+  static constexpr Attribute::AttrKind ID = Attribute::ReadNone;
+};
+
+/// An abstract interface for all nocapture attributes.
+struct AANoCapture : public AbstractAttribute {
+
+  /// See AbstractAttribute::AbstractAttribute(...).
+  AANoCapture(Value &V) : AbstractAttribute(V) {}
+
+  /// Return true if we know that the underlying value is not captured in its
+  /// respective scope.
+  virtual bool isKnownNoCapture() const = 0;
+
+  /// Return true if we assume that the underlying value is not captured in its
+  /// respective scope.
+  virtual bool isAssumedNoCapture() const = 0;
+
+  /// See the AbstractAttribute interface for information.
+  ///{
+
+  /// See AbstractState::getAttrKind().
+  Attribute::AttrKind getAttrKind() const override {
+    return ID;
+  }
+
+  /// See AbstractState::getAsStr().
+  const std::string getAsStr() const override {
+    return isAssumedNoCapture() ? "not-captured" : "maybe-captured";
+  };
+
+  ///}
+
+  /// The identifier used by the Attributor for this class of attributes.
+  static constexpr Attribute::AttrKind ID = Attribute::NoCapture;
+};
+
+/// An abstract interface for all dereferenceable(-or-null) attributes.
+struct AADereferenceableOrNull : public AbstractAttribute {
+
+  /// See AbstractAttribute::AbstractAttribute(...).
+  AADereferenceableOrNull(Value &V) : AbstractAttribute(V) {}
+
+  /// Return true if the associated value is known to be non-null.
+  virtual bool isKnownNonNull() const = 0;
+
+  /// Return true if we assume that the underlying value cannot be null. The
+  /// direction @p Dir decides if we look at the assumed information for forward
+  /// or backward traversal, or both, either inclusive or exclusive (see enum
+  /// Direction).
+  virtual bool isAssumedNonNull() const = 0;
+
+  /// Return the number of bytes that are known to be dereferenceable, if the
+  /// underlying value is not null, see isAssumedNonNull/isKnownNonNull.
+  virtual uint64_t getKnownDereferenceableBytes() const = 0;
+  virtual uint64_t getAssumedDereferenceableBytes() const = 0;
+
+  /// See the AbstractAttribute interface for information.
+  ///{
+
+  /// Return the LLVM-IR attribute kind, thus dereferenceable or
+  /// dereferenceable-or-null, depending on the internal state
+  /// (see AADereferenceableOrNull::isAssumedNonNull()).
+  Attribute::AttrKind getAttrKind() const override {
+    return isAssumedNonNull()
+               ? Attribute::Dereferenceable
+               : Attribute::DereferenceableOrNull;
+  }
+
+  uint64_t getAttrValue() const override {
+    return getKnownDereferenceableBytes();
+  }
+
+  /// Pretty print the attribute similar to the IR representation.
+  const std::string getAsStr() const override {
+    return (isAssumedNonNull() ? "dereferenceable("
+                                               : "dereferenceable-or-null(") +
+           std::to_string(getKnownDereferenceableBytes()) + "-" +
+           std::to_string(getAssumedDereferenceableBytes()) + ")";
+  }
+
+  ///}
+
+  /// The identifier used by the Attributor for this class of attributes.
+  static constexpr Attribute::AttrKind ID = Attribute::Dereferenceable;
+};
+
+/// An abstract attribute to determine the returned values of a function. If
+/// there is a unique returned value R, the manifest method will:
+///   - mark R with the "returned" attribute, if R is an argument.
+///   - replace the uses of call sites with R, if R is a constant.
+/// Even if there is no unique return value, or it is neither an argument or a
+/// constant, the information can be used for further forward propagation.
+struct AAReturnedValues : public AbstractAttribute {
+
+  /// See AbstractAttribute::AbstractAttribute(...).
+  AAReturnedValues(Function &F) : AbstractAttribute(F) {}
+
+  using ReturnedValuesTy = DenseSet<ReturnedValueInfo *>;
+
+  /// Iterators to walk through all possibly returned values.
+  ///{
+  using iterator = ReturnedValuesTy::iterator;
+  virtual iterator begin() = 0;
+  virtual iterator end() = 0;
+  ///}
+
+  virtual size_t getNumReturnValues() const =0;
+
+  /// Return the unique value returned by the associated function if one exists.
+  virtual Value *getUniqueReturnedValue(Attributor &A) const = 0;
+
+  virtual Attribute::AttrKind getAttrKind() const override {
+    return ID;
+  }
+
+  /// The identifier used by the Attributor for this class of attributes.
+  static constexpr Attribute::AttrKind ID = Attribute::Returned;
+};
+
+struct Attributor {
+
+  Attributor(AAGetterTy &AARGetter, DTGetterTy &DTGetter)
+      : AARGetter(AARGetter), DTGetter(DTGetter) {}
+
+  bool run(Module &M);
+
+  template <typename AAType = AbstractAttribute>
+  AAType *getAAFor(const Value &V, int ArgNo = -1,
+                   Attribute::AttrKind ID = AAType::ID);
+
+  void registerDependence(AbstractAttribute &From, AbstractAttribute &To);
+
+  AAResults &getAAR(Function &F) { return AARGetter(F); }
+  const DominatorTree &getDT(Function &F) { return DTGetter(F); }
+
+  bool foreachReturnedValue(Function &F, ReturnedValueCallbackTy &Callback);
+
+  template <typename StateTy>
+  bool forwardReturnedValues(StateTy &State, Function &F,
+                             ReturnedValueStateCallbackTy<StateTy> &Callback,
+                             bool LookThroughRecursion = false);
+
+  bool foreachCallSite(Function &F, CallSiteCallbackTy &Callback,
+                       bool RequireAllCallSites = true);
+
+  template <typename StateTy>
+  bool forwardCallSiteStates(StateTy &State, Function &F,
+                             CallSiteStateCallbackTy<StateTy> &Callback,
+                             bool RequireAllCallSites = true);
+
+private:
+
+  using AAVector = SmallVector<AbstractAttribute *, 64>;
+
+  template <typename AAType>
+  AAType &registerAA(AAType &AA, AASetVector *LiveAAs = nullptr);
+
+  /// Determine opportunities to derive attributes.
+  bool identifyAbstractAttributes(Function &F);
+
+  void tryToUseCallSite(CallSite CS, AASetVector &LiveAAs) ;
+
+  void tryToUseInstruction(Instruction &I, AASetVector &LiveAAs);
+
+  bool identifyExistingInformation(Function &F);
+
+  /// TODO
+  AAGetterTy &AARGetter;
+  DTGetterTy &DTGetter;
+
+  /// A map that represents the dependence graph between abstract attributes.
+  /// Each entry relates an abstract attribute A with all the abstract
+  /// attributes which used the optimistic information of A in the last fix
+  /// point iteration.
+  DenseMap<AbstractAttribute *, AASetVector> AADependenceMap;
+
+  AAVector AAsInSCC;
+
+  /// A map that allows to lookup abstract attributes based on llvm::Values and
+  /// a Attribute::AttrKind.
+  using KindToAbstractAttributeMap = DenseMap<unsigned, AbstractAttribute *>;
+  DenseMap<std::pair<const Value *, int>, KindToAbstractAttributeMap> AAMap;
+};
+
 /// The three kinds of memory access relevant to 'readonly' and
 /// 'readnone' attributes.
 enum MemoryAccessKind {
   MAK_ReadNone = 0,
   MAK_ReadOnly = 1,
   MAK_MayWrite = 2,
   MAK_WriteOnly = 3
 };

lib/Transforms/IPO/FunctionAttrs.cpp

 //===- FunctionAttrs.cpp - Pass which marks functions attributes ----------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 /// \file
 /// This file implements interprocedural passes which walk the
 /// call-graph deducing and/or propagating function attributes.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/IPO/FunctionAttrs.h"
+#include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SCCIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/CallGraphSCCPass.h"
 #include "llvm/Analysis/CaptureTracking.h"
+#include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LazyCallGraph.h"
+#include "llvm/Analysis/Loads.h"
+#include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Metadata.h"
+#include "llvm/IR/Operator.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Use.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/IPO.h"
 #include <cassert>
 #include <iterator>
-#include <map>
-#include <vector>
+#include <limits>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "functionattrs"
 
-STATISTIC(NumReadNone, "Number of functions marked readnone");
-STATISTIC(NumReadOnly, "Number of functions marked readonly");
-STATISTIC(NumWriteOnly, "Number of functions marked writeonly");
-STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
-STATISTIC(NumReturned, "Number of arguments marked returned");
-STATISTIC(NumReturnedWithCalls, "Number of arguments marked returned with calls");
-STATISTIC(NumReturnedKnownWithCalls,
-          "Number of returned values identified with call returns");
-STATISTIC(NumReturnedConstantWithCalls,
-          "Number of returned constant values identified with call returns");
-STATISTIC(NumReturnedKnown, "Number of returned values identified");
-STATISTIC(NumReturnedConstantKnown,
-          "Number of returned constant values identified");
-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(NumNoRecurse, "Number of functions marked as norecurse");
-STATISTIC(NumNoUnwind, "Number of functions marked as nounwind");
+STATISTIC(NumReadNone, "Old: Number of functions marked readnone");
+STATISTIC(NumReadOnly, "Old: Number of functions marked readonly");
+STATISTIC(NumWriteOnly, "Old: Number of functions marked writeonly");
+STATISTIC(NumNoCapture, "Old: Number of arguments marked nocapture");
+STATISTIC(NumReturned, "Old: Number of arguments marked returned");
+STATISTIC(NumReadNoneArg, "Old: Number of arguments marked readnone");
+STATISTIC(NumReadOnlyArg, "Old: Number of arguments marked readonly");
+STATISTIC(NumNoAlias, "Old: Number of function returns marked noalias");
+STATISTIC(NumNonNullReturn, "Old: Number of function returns marked nonnull");
+STATISTIC(NumNoRecurse, "Old: Number of functions marked as norecurse");
+STATISTIC(NumNoUnwind, "Old: Number of functions marked as nounwind");
+
+STATISTIC(NumSufficientConditionsRegistered,
+          "Number of sufficient conditions registered");
+STATISTIC(NumMaxIterationsPerLevelReached,
+          "Number of times max iterations per lvl were reached");
+
+STATISTIC(NumFnWithExactDefinition,
+          "Number of function with exact definitions");
+STATISTIC(NumFnWithoutExactDefinition,
+          "Number of function without exact definitions");
+
+STATISTIC(NumFnReturnNoAlias,
+          "Number of function return values marked no-alias");
+STATISTIC(NumFnArgumentNoAlias, "Number of function arguments marked no-alias");
+
+STATISTIC(NumFnReturntNonNull,
+          "Number of function return values marked non-null");
+STATISTIC(NumFnArgumentNonNull, "Number of function arguments marked non-null");
+STATISTIC(NumCSArgumentNonNull,
+          "Number of call site arguments marked non-null");
+STATISTIC(NumLoadMetadataNonNull, "Number of load results marked non-null");
+
+STATISTIC(NumFnUniqueReturned, "Number of function with unique return");
+STATISTIC(NumFnArgumentReturned,
+          "Number of function arguments marked returned");
+STATISTIC(NumFnReturnedConstantsReplaced,
+          "Number of function returned constants replaced");
+
+STATISTIC(NumFnArgumentNoCapture, "Number of function arguments marked no-capture");
+
+STATISTIC(NumFnsReadNone, "Number of functions marked read-none");
+STATISTIC(NumFnsReadOnly, "Number of functions marked read-only");
+STATISTIC(NumFnsWriteOnly, "Number of functions marked write-only");
+
+STATISTIC(NumArgReadNone, "Number of function arguments marked read-none");
+STATISTIC(NumArgReadOnly, "Number of function arguments marked read-only");
+STATISTIC(NumArgWriteOnly, "Number of function arguments marked write-only");
+
+STATISTIC(NumFnReturnDereferenceable,
+          "Number of function return values marked dereferenceable");
+STATISTIC(NumFnArgumentDereferenceable,
+          "Number of function arguments marked dereferenceable");
+STATISTIC(NumCSArgumentDereferenceable,
+          "Number of call site arguments marked dereferenceable");
+STATISTIC(NumFnReturnDereferenceableOrNull,
+          "Number of function return values marked dereferenceable-or-null");
+STATISTIC(NumFnArgumentDereferenceableOrNull,
+          "Number of function arguments marked dereferenceable-or-null");
+STATISTIC(NumCSArgumentDereferenceableOrNull,
+          "Number of call site arguments marked dereferenceable-or-null");
 
 // FIXME: This is disabled by default to avoid exposing security vulnerabilities
 // in C/C++ code compiled by clang:
 // http://lists.llvm.org/pipermail/cfe-dev/2017-January/052066.html
 static cl::opt<bool> EnableNonnullArgPropagation(
     "enable-nonnull-arg-prop", cl::Hidden,
     cl::desc("Try to propagate nonnull argument attributes from callsites to "
              "caller functions."));
 
 static cl::opt<bool> DisableNoUnwindInference(
     "disable-nounwind-inference", cl::Hidden,
     cl::desc("Stop inferring nounwind attribute during function-attrs pass"));
 
+static cl::opt<unsigned> MAX_ATTRIBUTOR_ITERATIONS_PER_LVL(
+    "functionattrs-attributor-iterations-per-lvl", cl::Hidden,
+    cl::desc(
+        "Perform at most this many iterations to find a fix point per level."),
+    cl::init(100));
+
 namespace {
+static const bool CHANGED = true;
+static const bool UNCHANGED = false;
+
+static raw_ostream &operator<<(raw_ostream &OS, const ReturnedValueInfo &RV) {
+  OS << "RV: " << *RV.V;
+  if (RV.CtxI) {
+    OS << " @ " << RV.CtxI;
+    OS << " @ " << *RV.CtxI;
+  }
+  if (RV.RV)
+    OS << "\n\t-> via " << *RV.RV;
+  return OS;
+}
+
+template <typename StateTy>
+using StateCache = DenseMap<Value *, Optional<StateTy>>;
+
+template <typename StateTy, typename CallbackTy, typename... ArgsTy>
+StateTy cachedPointerTraversal(StateCache<StateTy> &Cache, Value *V,
+                               CallbackTy &&CB, ArgsTy &&... args) {
+  V = V->stripPointerCasts();
+
+  Optional<StateTy> &CachedResult = Cache[V];
+  if (CachedResult.hasValue())
+    return CachedResult.getValue();
+  CachedResult = StateTy::bot();
+
+  StateTy Result = StateTy::bot();
+  if (auto *PHI = dyn_cast<PHINode>(V)) {
+
+    for (Value *Op : PHI->operands())
+      Result.getLowerBound(
+          cachedPointerTraversal(Cache, Op, CB, std::forward<ArgsTy>(args)...));
 
-using SCCNodeSet = SmallSetVector<Function *, 8>;
+  } else if (auto *Select = dyn_cast<SelectInst>(V)) {
+    Result = cachedPointerTraversal(Cache, Select->getTrueValue(), CB,
+                                    std::forward<ArgsTy>(args)...);
+    Result.getLowerBound(cachedPointerTraversal(
+        Cache, Select->getFalseValue(), CB, std::forward<ArgsTy>(args)...));
+  } else {
+    Result = CB(V, std::forward<ArgsTy>(args)...);
+  }
+
+  Cache[V] = Result;
+  return Result;
+}
 
 } // end anonymous namespace
 
+raw_ostream &llvm::operator<<(raw_ostream &OS,
+                              AbstractAttribute::ManifestPosition AP) {
+  switch (AP) {
+  case AbstractAttribute::MP_FUNCTION:
+    return OS << "fnc";
+  case AbstractAttribute::MP_RETURNED:
+    return OS << "ret";
+  case AbstractAttribute::MP_ARGUMENT:
+    return OS << "arg";
+  case AbstractAttribute::MP_CALL_SITE_ARGUMENT:
+  case AbstractAttribute::MP_CALL_SITE_ARGUMENT_NOT_IR:
+    return OS << "csa";
+  case AbstractAttribute::MP_INSTRUCTION_METADATA:
+    return OS << "imd";
+  }
+  llvm_unreachable("Unknown attribute position!");
+}
+
+struct llvm::AbstractState {
+
+  virtual void resetAssumed() = 0;
+
+  /// Return if this abstract state is the worst possible.
+  virtual bool isWorstPossible() const = 0;
+
+  /// Return if this abstract state is the best possible.
+  virtual bool isBestPossible() const = 0;
+
+  /// Fix this abstract state to the known state, thus eliminate the optimism.
+  virtual void revertToKnown() = 0;
+
+  /// Return if this abstract state is fixed, thus does not need to be updated
+  /// if information changes as it cannot change itself.
+  virtual bool isAtFixpoint() const = 0;
+
+  /// Indicate that the abstract state is at a fixpoint. This will usually make
+  /// the assumed state the known state and cause "isAtFixpoint()" to be true.
+  virtual void indicateFixpoint() = 0;
+
+  /// Return true if the state is in a consistent state. Non-consistent states
+  /// indicate an error in the analysis.
+  virtual bool isConsistent() const = 0;
+};
+
+raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractState &State) {
+  return OS << (State.isWorstPossible()
+                    ? "top"
+                    : (State.isBestPossible() ? "fix" : ""));
+}
+
+template <typename StateLeftTy, typename StateRightTy>
+struct PairState : public AbstractState {
+
+  PairState() {}
+  PairState(const StateLeftTy &Left, const StateRightTy &Right)
+      : Left(Left), Right(Right) {}
+
+  virtual void resetAssumed() override {
+    Left.resetAssumed();
+    Right.resetAssumed();
+  }
+
+  /// Return if this abstract state is the worst possible.
+  virtual bool isWorstPossible() const override {
+    return Left.isWorstPossible() && Right.isWorstPossible();
+  }
+
+  /// Return if this abstract state is the best possible.
+  virtual bool isBestPossible() const override {
+    return Left.isBestPossible() && Right.isBestPossible();
+  }
+
+  virtual bool isConsistent() const override {
+    return Left.isConsistent() && Right.isConsistent();
+  }
+
+  virtual void getLowerBound(const PairState &Other) {
+    Left.getLowerBound(Other.Left);
+    Right.getLowerBound(Other.Right);
+    assert(isConsistent());
+  }
+
+  virtual void getUpperBound(const AbstractState &Other) {
+    Left.getUpperBound(static_cast<const PairState &>(Other).Left);
+    Right.getUpperBound(static_cast<const PairState &>(Other).Right);
+  }
+
+  virtual bool combine(const AbstractState &Other) {
+    bool Changed = false;
+    Changed |= Left.combine(static_cast<const PairState &>(Other).Left);
+    Changed |= Right.combine(static_cast<const PairState &>(Other).Right);
+    return Changed;
+  }
+
+  virtual bool operator==(const PairState &Other) const {
+    return Left == Other.Left && Right == Other.Right;
+  }
+  virtual bool operator!=(const PairState &Other) const {
+    return !(*this == Other);
+  }
+
+  virtual void revertToKnown() override {
+    Left.revertToKnown();
+    Right.revertToKnown();
+  }
+
+  virtual bool isAtFixpoint() const override {
+    return Left.isAtFixpoint() && Right.isAtFixpoint();
+  }
+  virtual void indicateFixpoint() override {
+    Left.indicateFixpoint();
+    Right.indicateFixpoint();
+  }
+
+  StateLeftTy Left;
+  StateRightTy Right;
+};
+
+template <typename BaseTy, BaseTy InitKnown, BaseTy InitAssumed>
+struct IntegerState : public AbstractState {
+
+  IntegerState() : Known(InitKnown), Assumed(InitAssumed) {
+    assert(isConsistent());
+  }
+
+  IntegerState(BaseTy KnownValue) : IntegerState(KnownValue, InitAssumed) {}
+
+  IntegerState(BaseTy KnownValue, BaseTy AssumedValue)
+      : Known(KnownValue), Assumed(AssumedValue) {
+    assert(isConsistent());
+  }
+
+  bool isConsistent() const override { return Assumed >= Known; }
+
+  void getLowerBound(const IntegerState &Other) {
+    Known = std::min(Known, Other.Known);
+    Assumed = std::min(Assumed, Other.Assumed);
+    assert(isConsistent());
+  }
+
+  void getUpperBound(const IntegerState &Other) {
+    Assumed = std::max(Assumed, Other.Assumed);
+    Known = std::max(Known, Other.Known);
+    Assumed = std::max(Known, Assumed);
+    assert(isConsistent());
+  }
+
+  // virtual bool combine(const AbstractState &Other) override{
+  // return combine(static_cast<const IntegerState &>(Other));
+  //}
+  bool combine(const IntegerState &Other) {
+    auto OldState = *this;
+    Assumed = std::min(Assumed, Other.Assumed);
+    Known = std::max(Known, Other.Known);
+    Assumed = std::max(Known, Assumed);
+    assert(isConsistent());
+    return *this == OldState ? UNCHANGED : CHANGED;
+  }
+
+  bool operator==(const IntegerState &Other) const {
+    return Known == Other.Known && Assumed == Other.Assumed;
+  }
+  bool operator!=(const IntegerState &Other) const { return !(*this == Other); }
+
+  void resetAssumed() override {
+    Assumed = InitAssumed;
+    assert(isConsistent());
+  }
+
+  bool isWorstPossible() const override { return Assumed == InitKnown; }
+
+  bool isBestPossible() const override { return Known == InitAssumed; }
+
+  void revertToKnown() override {
+    Assumed = Known;
+    assert(isConsistent());
+  }
+
+  bool isAtFixpoint() const override { return Assumed == Known; }
+
+  void indicateFixpoint() override {
+    Known = Assumed;
+    assert(isConsistent());
+  }
+
+  // virtual void mergeKnownState(const AbstractState &State) override {
+  // Known = std::max(Known, static_cast<const IntegerState &>(State).Known);
+  //}
+
+  static IntegerState bot() { return IntegerState(InitAssumed, InitAssumed); }
+  static IntegerState top() { return IntegerState(InitKnown, InitKnown); }
+
+  BaseTy getKnown() const { return Known; }
+  BaseTy getAssumed() const { return Assumed; }
+
+  void setKnown(BaseTy NewKnown) {
+    Known = NewKnown;
+    Assumed = std::max(Assumed, Known);
+  }
+
+  void setAssumed(BaseTy NewAssumed) { Assumed = NewAssumed; }
+
+private:
+  BaseTy Known;
+  BaseTy Assumed;
+};
+
+using BooleanState = IntegerState<bool, 0, 1>;
+
+raw_ostream &operator<<(raw_ostream &OS, const BooleanState &State) {
+  return OS << (State.getKnown() ? "known"
+                                 : (State.getAssumed() ? "assumed" : "top"));
+}
+
+template <typename BaseTy, BaseTy InitKnown, BaseTy InitAssumed>
+raw_ostream &
+operator<<(raw_ostream &OS,
+           const IntegerState<BaseTy, InitKnown, InitAssumed> &State) {
+  return OS << " {" << State.getKnown() << "-" << State.getAssumed() << "} "
+            << static_cast<const AbstractState &>(State);
+}
+
+/// Helper to dump abstract attributes into a stream.
+raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractAttribute &AA) {
+  AA.print(OS);
+  return OS;
+}
+
+/// Hook for the Attributor to trigger an update of the internal state.
+/// If this attribute is already fixed, nothing happens, if it is not, the
+/// environment was CHANGED and we have to determine if the current
+/// information is still valid or adjust it otherwise. There is no explicit
+/// return value but the internal "CHANGED" variable is set accordingly.
+bool AbstractAttribute::update(Attributor &A, Direction Dir) {
+  if (getState().isAtFixpoint())
+    return UNCHANGED;
+
+  LLVM_DEBUG(errs() << "RUN updateImpl on: " << *this << "\n");
+
+  bool Changed = UNCHANGED;
+  if (isImplied(A, Dir, Changed))
+    return Changed;
+
+  Changed = updateImpl(A, Dir);
+  LLVM_DEBUG(errs() << "[" << Changed << "] updateImpl on: " << *this << "\n");
+
+  return Changed;
+}
+
+/// Hook for the Attributor to trigger the manifestation of the information
+/// represented by the abstract attribute in the LLVM-IR.
+bool AbstractAttribute::manifest(Attributor &A) {
+  if (getState().isWorstPossible())
+    return false;
+
+  LLVMContext &Ctx = V.getContext();
+
+  switch (getManifestPosition()) {
+  case MP_FUNCTION: {
+    Function &F = cast<Function>(getAnchoredValue());
+    if (F.hasFnAttribute(getAttrKind())) {
+      Attribute Attr = F.getFnAttribute(getAttrKind());
+      if (!Attr.isIntAttribute() || Attr.getValueAsInt() >= getAttrValue())
+        return false;
+    }
+
+    F.addFnAttr(Attribute::get(Ctx, getAttrKind(), getAttrValue()));
+    break;
+  }
+  case MP_RETURNED: {
+    Function &F = cast<Function>(getAnchoredValue());
+    if (F.hasAttribute(AttributeList::ReturnIndex, getAttrKind())) {
+      Attribute Attr =
+          F.getAttribute(AttributeList::ReturnIndex, getAttrKind());
+      if (!Attr.isIntAttribute() || Attr.getValueAsInt() >= getAttrValue())
+        return false;
+    }
+
+    F.addAttribute(AttributeList::ReturnIndex,
+                   Attribute::get(Ctx, getAttrKind(), getAttrValue()));
+    break;
+  }
+  case MP_ARGUMENT: {
+    Argument &A = cast<Argument>(getAnchoredValue());
+    if (A.hasAttribute(getAttrKind())) {
+      Attribute Attr = A.getParent()->getAttributes().getParamAttr(
+          getArgumentNo(), getAttrKind());
+      if (!Attr.isIntAttribute() || Attr.getValueAsInt() >= getAttrValue())
+        return false;
+    }
+
+    A.addAttr(Attribute::get(Ctx, getAttrKind(), getAttrValue()));
+    break;
+  }
+  case MP_INSTRUCTION_METADATA: {
+    Instruction &I = cast<Instruction>(getAnchoredValue());
+    assert(0 <= getAttrValue() && getAttrValue() <= 1);
+    if (I.getMetadata(getMetadataID()))
+      return false;
+    I.setMetadata(getMetadataID(), getMetadataNode());
+    break;
+  }
+  case MP_CALL_SITE_ARGUMENT: {
+    CallSite CS(&getAnchoredValue());
+    assert(0 <= getAttrValue() && getAttrValue() <= 1);
+    bool Changed = true;
+    if (CS.paramHasAttr(getArgumentNo(), getAttrKind())) {
+      Attribute Attr =
+          CS.getAttributes().getParamAttr(getArgumentNo(), getAttrKind());
+      if (!Attr.isIntAttribute() || Attr.getValueAsInt() >= getAttrValue())
+        Changed = false;
+    }
+
+    CS.addParamAttr(getArgumentNo(), getAttrKind());
+    if (!Changed)
+      return false;
+    break;
+  }
+  case MP_CALL_SITE_ARGUMENT_NOT_IR:
+    return false;
+    break;
+  }
+
+  // Bookkeeping.
+  if (auto *Stats = getStatisticObj())
+    (*Stats)++;
+
+  return true;
+}
+
+bool AbstractAttribute::isImpliedBy(AbstractAttribute &AA, Direction Dir,
+                                    bool &Changed) {
+  assert(AA.getAttrKind() == getAttrKind());
+
+  const BooleanState &OtherState =
+      static_cast<const BooleanState &>(AA.getState());
+  static_cast<BooleanState &>(getState()).setKnown(OtherState.getKnown());
+
+  if (!getState().isBestPossible())
+    return false;
+
+  Changed = true;
+  return true;
+}
+
+bool AbstractAttribute::isImplied(Attributor &A, Direction Dir, bool &Changed) {
+
+  AASetVector &AAs = Dir == FORWARD ? PrecedingAAs : SucceedingAAs;
+  // errs() << "isImplied check with " << AAs.size() << " AAs!\n";
+
+  if (AAs.empty())
+    return false;
+
+  LLVM_DEBUG(dbgs() << "Check if one of the " << AAs.size()
+                    << (Dir == FORWARD ? "preceding" : "succeeding")
+                    << " AAs imply this one!\n");
+
+  for (AbstractAttribute *AA : AAs) {
+    LLVM_DEBUG(dbgs() << " -- Check " << *AA << "\n");
+    if (isImpliedBy(*AA, Dir, Changed))
+      return true;
+  }
+
+  LLVM_DEBUG(dbgs() << " -- Failed to find implying AA!\n");
+  return false;
+}
+
+void AbstractAttribute::registerPrecedingAndSucceedingAAs(
+    const AASetVector &AAs, bool Preceding, bool Succeeding,
+    bool StripInbounds) {
+
+  assert(Preceding | Succeeding);
+
+  if (AAs.empty())
+    return;
+
+  // errs() << "rPredAAs [" << AAs.size() << "]: for " << *this << "\n";
+
+  Value *BasePtr = &getAssociatedValue();
+  // errs() << *BasePtr << ":";
+  if (StripInbounds)
+    BasePtr = BasePtr->stripInBoundsOffsets();
+  // errs() << *BasePtr << "\n";
+
+  const auto &Range = make_range(AAs.rbegin(), AAs.rend());
+  for (AbstractAttribute *AA : Range) {
+    if (AA->getAttrKind() != getAttrKind())
+      continue;
+
+    Value *AABasePtr = &AA->getAssociatedValue();
+    // errs() << *AABasePtr << ":";
+
+    if (StripInbounds)
+      AABasePtr = AABasePtr->stripInBoundsOffsets();
+
+    // errs() << *AABasePtr << "\n";
+    if (BasePtr != AABasePtr)
+      continue;
+
+    if (Preceding)
+      this->PrecedingAAs.insert(AA);
+
+    if (Succeeding)
+      AA->SucceedingAAs.insert(this);
+  }
+}
+
+void AbstractAttribute::print(raw_ostream &OS) const {
+  const AbstractState &State = getState();
+  if (isa<Function>(V))
+    OS << "[" << getManifestPosition()
+       << (getArgumentNo() >= 0 ? "(" + std::to_string(getArgumentNo()) + ")"
+                                : "")
+       << "][" << getAsStr() << "=" << getState() << "][" << V.getName() << "]";
+  else
+    OS << "[" << getManifestPosition()
+       << (getArgumentNo() >= 0 ? "(" + std::to_string(getArgumentNo()) + ")"
+                                : "")
+       << "][" << getAsStr() << "=" << getState() << "][" << V << "]";
+}
+
+/// ------------------------ No-Null Attributes -------------------------------
+
+/// A class to hold the state of for non-null attributes.
+struct AANonNullImpl : public AANonNull {
+
+  /// Constructor that takes the value this attribute is anchored with (@p V),
+  /// the address space of the associated value, as well as the function this
+  /// attribute is related to.
+  AANonNullImpl(Value &V, unsigned AddrSpace, Function &F);
+
+  /// Return true if the associated value is known to be non-null.
+  bool isKnownNonNull() const override { return State.getKnown(); }
+
+  /// Return true if we assume that the underlying value cannot be null.
+  bool isAssumedNonNull() const override { return State.getAssumed(); }
+
+  /// See the AbstractAttribute interface for information.
+  ///{
+
+  virtual bool isImpliedBy(AbstractAttribute &OtherAA, Direction Dir,
+                           bool &Changed) override;
+
+  /// See AbstractAttribute::useKnownAccessInformation(...).
+  virtual void useKnownAccessInformation(uint64_t Length,
+                                         const APInt &Offset) override;
+
+  /// See AbstractState::getState().
+  ///{
+  virtual AbstractState &getState() override { return State; }
+  virtual const AbstractState &getState() const override { return State; }
+  ///}
+
+  ///}
+
+  /// Encapsulate the name of the underlying abstract state.
+  using NonNullStateTy = BooleanState;
+
+  /// Check the value @p V for non-nullness and update the internal state
+  /// (IsAssumedNonNull.
+  NonNullStateTy
+  checkValueForNonNullness(Value *V, Attributor &A, Direction Dir,
+                           Instruction *CtxI,
+                           DenseMap<Value *, Optional<NonNullStateTy>> &Cache);
+
+  /// TODO
+  static NonNullStateTy checkExactValueForNonNullness(Value *V, Attributor &A,
+                                                      Direction Dir,
+                                                      Instruction *CtxI,
+                                                      Function &F);
+
+protected:
+  /// The function associated with this abstract state.
+  Function &F;
+
+  /// Flag that indicates if, for the underlying value, nullptr is inaccessible.
+  const bool NullPtrIsUndefined;
+
+  /// The underlying abstract state for all AANonNullImpl classes.
+  NonNullStateTy State;
+};
+
+AANonNullImpl::AANonNullImpl(Value &V, unsigned AddrSpace, Function &F)
+    : AANonNull(V), F(F),
+      NullPtrIsUndefined(!NullPointerIsDefined(&F, AddrSpace)) {}
+
+void AANonNullImpl::useKnownAccessInformation(uint64_t Length,
+                                              const APInt &Offset) {
+  if (isKnownNonNull() || !Length || !NullPtrIsUndefined)
+    return;
+
+  State.setKnown(true);
+  assert(State.isAtFixpoint());
+}
+
+#if 0
+bool AANonNullImpl::checkDerefOrNullAA(Attributor &A, Direction Dir) {
+  assert(!isKnownNonNull());
+
+  // As long as the AADereferenceableOrNull assumes the associated value is
+  // non-null, we do not have to analyze anything. If that attribute knows it is
+  // non-null, we can copy that information and found a fix point.
+  auto *DerefOrNullAA =
+      A.getAAFor<AADereferenceableOrNull>(getAnchoredValue(), getArgumentNo());
+  //errs() << "DerefOrNullAA for " << *this << "\n--> " << DerefOrNullAA << "\n";
+  //if (DerefOrNullAA)
+    //errs() << "--> " << *DerefOrNullAA
+           //<< " :: " << DerefOrNullAA->isAssumedNonNull() << "\n";
+  if (!DerefOrNullAA || !DerefOrNullAA->isAssumedNonNull())
+    return false;
+
+  if (DerefOrNullAA->isKnownNonNull()) {
+    State.setKnown(true);
+    assert(State.isAtFixpoint());
+  } else {
+    // addUsedAA(*DerefOrNullAA);
+  }
+
+  return true;
+}
+#endif
+
+AANonNullImpl::NonNullStateTy AANonNullImpl::checkValueForNonNullness(
+    Value *V, Attributor &A, Direction Dir, Instruction *CtxI,
+    DenseMap<Value *, Optional<NonNullStateTy>> &Cache) {
+
+  NonNullStateTy Result = cachedPointerTraversal(
+      Cache, V, checkExactValueForNonNullness, A, Dir, CtxI, F);
+
+  // TODO: This should not be needed as a similar check is performed in the
+  //       isKnownNonZero call below. However, there we only look through
+  //       in-bounds GEPs. Because looking through all GEPs was the default
+  //       implementation for non-null interference for a while now, this code
+  //       is put in place to avoid regressions.
+  if (const auto *GEP = dyn_cast<GEPOperator>(V)) {
+    if (!Result.getKnown())
+      Result.getUpperBound(
+          checkValueForNonNullness(GEP->getOperand(0), A, Dir, CtxI, Cache));
+  }
+
+  return Result;
+}
+
+AANonNullImpl::NonNullStateTy AANonNullImpl::checkExactValueForNonNullness(
+    Value *V, Attributor &A, Direction Dir, Instruction *CtxI, Function &F) {
+
+  {
+    auto *NonNullAA = A.getAAFor<AANonNullImpl>(*V);
+    if (NonNullAA && NonNullAA->isAssumedNonNull())
+      return NonNullAA->State;
+  }
+
+  const DominatorTree &DT = A.getDT(F);
+  const DataLayout &DL = F.getParent()->getDataLayout();
+  if (isKnownNonZero(V, DL, 0, nullptr, CtxI, &DT))
+    return NonNullStateTy::bot();
+
+  if (V->getType()->isPointerTy()) {
+
+    bool isKnownNonNull = false;
+    if (V->getPointerDereferenceableBytes(DL, isKnownNonNull))
+      if (isKnownNonNull)
+        return NonNullStateTy::bot();
+
+    if (!NullPointerIsDefined(&F, V->getType()->getPointerAddressSpace()) &&
+        isDereferenceablePointer(V, DL))
+      return NonNullStateTy::bot();
+  }
+
+  return NonNullStateTy::top();
+}
+
+bool AANonNullImpl::isImpliedBy(AbstractAttribute &OtherAA, Direction Dir,
+                                bool &Changed) {
+  Attribute::AttrKind OtherKind = OtherAA.getAttrKind();
+
+  if (OtherKind == getAttrKind())
+    return AbstractAttribute::isImpliedBy(OtherAA, Dir, Changed);
+
+  assert(OtherKind == Attribute::Dereferenceable ||
+         OtherKind == Attribute::DereferenceableOrNull);
+
+  auto &OtherDerefOrNullAA = static_cast<AADereferenceableOrNull &>(OtherAA);
+  State.setKnown(OtherDerefOrNullAA.isKnownNonNull());
+
+  if (!isKnownNonNull())
+    return false;
+
+  Changed = true;
+  return true;
+}
+
+/// ------------------------ No-Null Arguments --------------------------------
+
+/// An AA to represent the non-null argument attribute.
+struct AANonNullArgument final : public AANonNullImpl {
+
+  /// See AANonNullImpl::AANonNullImpl(...).
+  AANonNullArgument(Argument &Arg)
+      : AANonNullImpl(Arg, Arg.getType()->getPointerAddressSpace(),
+                      *Arg.getParent()) {
+
+    // Determine if the IR already provides enough information.
+    if (Arg.hasNonNullAttr()) {
+      State.setKnown(true);
+      assert(State.isAtFixpoint());
+    }
+  }
+
+  /// See the AbstractAttribute interface for information.
+  ///{
+
+  /// See AbstractAttribute::updateImpl(Attributor &A, Direction Dir).
+  virtual bool updateImpl(Attributor &A, Direction Dir) override;
+
+  /// See AbstractAttribute::getArgumentNo().
+  virtual int getArgumentNo() const override {
+    return cast<Argument>(getAnchoredValue()).getArgNo();
+  }
+
+  /// See AbstractAttribute::getManifestPosition().
+  virtual ManifestPosition getManifestPosition() const override {
+    return MP_ARGUMENT;
+  };
+
+  /// See AbstractAttribute::getStatisticObj().
+  virtual Statistic *getStatisticObj() const override {
+    return &NumFnArgumentNonNull;
+  }
+
+  ///}
+};
+
+bool AANonNullArgument::updateImpl(Attributor &A, Direction Dir) {
+  if (Dir == BACKWARD) {
+    State.revertToKnown();
+    return CHANGED;
+  }
+
+  Argument &Arg = cast<Argument>(getAnchoredValue());
+
+  const DataLayout &DL = F.getParent()->getDataLayout();
+  unsigned ArgNo = Arg.getArgNo();
+  SmallPtrSet<Value *, 16> Visited;
+
+  bool AllCallSitesAreKnownNonNull = true;
+
+  // Callback function
+  CallSiteCallbackTy CallSiteCheck = [&](CallSite CS) {
+    assert(CS && "Sanity check: Call site was not initialized properly!");
+
+    if (CS.paramHasAttr(ArgNo, Attribute::NonNull))
+      return true;
+
+    AANonNull *NonNullCSArgAA =
+        A.getAAFor<AANonNull>(*CS.getInstruction(), getArgumentNo());
+    if (!NonNullCSArgAA || !NonNullCSArgAA->isAssumedNonNull())
+      return false;
+
+    if (!NonNullCSArgAA->isKnownNonNull())
+      AllCallSitesAreKnownNonNull = false;
+
+    return true;
+  };
+
+  // If no abstract argument was found look at the call sites.
+  if (A.foreachCallSite(F, CallSiteCheck)) {
+    if (AllCallSitesAreKnownNonNull)
+      State.indicateFixpoint();
+
+    return UNCHANGED;
+  }
+
+  State.revertToKnown();
+  return CHANGED;
+}
+
+/// ------------------- No-Null Call Site Arguments ----------------------------
+
+/// An AA to represent the non-null attribute for a call site argument.
+struct AANonNullCallSiteArgument final : public AANonNullImpl {
+
+  /// See AANonNullImpl::AANonNullImpl(...).
+  AANonNullCallSiteArgument(CallSite CS, unsigned ArgNo)
+      : AANonNullImpl(
+            *CS.getInstruction(),
+            CS.getArgOperand(ArgNo)->getType()->getPointerAddressSpace(),
+            *CS.getCaller()),
+        ArgNo(ArgNo) {
+
+    // Determine if the IR already provides enough information.
+    if (CS.paramHasAttr(ArgNo, getAttrKind()))
+      State.indicateFixpoint();
+  }
+
+  /// See the AbstractAttribute interface for information.
+  ///{
+
+  /// See AbstractAttribute::updateImpl(Attributor &A, Direction Dir).
+  virtual bool updateImpl(Attributor &A, Direction Dir) override;
+
+  /// See AbstractAttribute::getArgumentNo().
+  virtual int getArgumentNo() const override { return ArgNo; }
+
+  /// See AbstractAttribute::getAssociatedValue().
+  ///{
+  Value &getAssociatedValue() override {
+    return *CallSite(&getAnchoredValue()).getArgOperand(getArgumentNo());
+  }
+  const Value &getAssociatedValue() const override {
+    return *ImmutableCallSite(&getAnchoredValue())
+                .getArgOperand(getArgumentNo());
+  }
+  ///}
+
+  /// See AbstractAttribute::getManifestPosition().
+  virtual ManifestPosition getManifestPosition() const override {
+    return MP_CALL_SITE_ARGUMENT;
+  };
+
+  /// See AbstractAttribute::getStatisticObj().
+  virtual Statistic *getStatisticObj() const override {
+    return &NumCSArgumentNonNull;
+  }
+
+  ///}
+
+private:
+  /// The underlying value is the argument at position "ArgNo" of the call site
+  /// that is used as the underyling anchor. See
+  /// AbstractAttribute::getAssociatedValue().
+  const unsigned ArgNo;
+};
+
+bool AANonNullCallSiteArgument::updateImpl(Attributor &A, Direction Dir) {
+  CallSite CS(&getAnchoredValue());
+  Value *V = CS.getArgOperand(getArgumentNo());
+
+  if (Dir == BACKWARD) {
+    Function *Callee = CS.getCalledFunction();
+    assert(Callee && Callee->arg_size() > getArgumentNo());
+
+    Argument *FnArg = Callee->arg_begin() + getArgumentNo();
+    auto *NonNullFnArgAA = A.getAAFor<AANonNull>(*FnArg);
+
+    if (NonNullFnArgAA && NonNullFnArgAA->isAssumedNonNull()) {
+      State.setKnown(NonNullFnArgAA->isKnownNonNull());
+      // errs() << "<- backward from arg: " << *NonNullFnArgAA << "\n";
+      return /* Changed */ State.getKnown();
+    }
+    State.revertToKnown();
+    return CHANGED;
+  }
+
+  Instruction *CSInst = CS.getInstruction();
+  DenseMap<Value *, Optional<NonNullStateTy>> Cache;
+  NonNullStateTy ValState = checkValueForNonNullness(V, A, Dir, CSInst, Cache);
+  // errs() << "dir: " << Dir << " checkValueForNonNullness: " << ValState <<
+  // "\n";
+
+  if (ValState == State)
+    return UNCHANGED;
+
+  State = ValState;
+  return CHANGED;
+}
+
+/// ----------------------- No-Null Load Results -------------------------------
+
+/// An AA to represent the non-null metadata for a memory instruction.
+struct AANonNullLoadResult final : public AANonNullImpl {
+
+  /// See AANonNullImpl::AANonNullImpl(...).
+  AANonNullLoadResult(LoadInst &I)
+      : AANonNullImpl(I, I.getType()->getPointerAddressSpace(),
+                      *I.getFunction()) {
+
+    // Determine if the IR already provides enough information.
+    if (I.getMetadata(getMetadataID()))
+      State.indicateFixpoint();
+  }
+
+  virtual MDNode *getMetadataNode() const override {
+    return MDNode::get(getAnchoredValue().getContext(), {});
+  }
+  virtual unsigned getMetadataID() const override {
+    return LLVMContext::MD_nonnull;
+  }
+
+  /// See AbstractAttribute::getManifestPosition().
+  virtual ManifestPosition getManifestPosition() const override {
+    return MP_INSTRUCTION_METADATA;
+  };
+
+  /// See AbstractAttribute::getStatisticObj().
+  virtual Statistic *getStatisticObj() const override {
+    return &NumLoadMetadataNonNull;
+  }
+
+private:
+  /// See AbstractAttribute::updateImpl(Attributor &A, Direction Dir).
+  virtual bool updateImpl(Attributor &A, Direction Dir) override;
+};
+
+bool AANonNullLoadResult::updateImpl(Attributor &A, Direction Dir) {
+  // LoadInst &Load = cast<LoadInst>(getAnchoredValue());
+
+  State.revertToKnown();
+  return CHANGED;
+}
+
+/// ---------------------- No-Null Return Values  ------------------------------
+
+/// An AA to represent the non-null function return attribute.
+struct AANonNullReturned final : public AANonNullImpl {
+
+  /// See AANonNullImpl::AANonNullImpl(...).
+  AANonNullReturned(Function &F)
+      : AANonNullImpl(F, F.getReturnType()->getPointerAddressSpace(), F) {
+
+    // Determine if the IR already provides enough information.
+    if (F.hasAttribute(AttributeList::ReturnIndex, getAttrKind()))
+      State.indicateFixpoint();
+  }
+
+  /// See AbstractAttribute::getManifestPosition().
+  virtual ManifestPosition getManifestPosition() const override {
+    return MP_RETURNED;
+  };
+
+  /// See AbstractAttribute::getStatisticObj().
+  virtual Statistic *getStatisticObj() const override {
+    return &NumFnReturntNonNull;
+  }
+
+  /// See AbstractAttribute::updateImpl(Attributor &A, Direction Dir).
+  virtual bool updateImpl(Attributor &A, Direction Dir) override;
+};
+
+bool AANonNullReturned::updateImpl(Attributor &A, Direction Dir) {
+  if (Dir == FORWARD) {
+    // Check all values returned by this function.
+    DenseMap<Value *, Optional<NonNullStateTy>> Cache;
+    ReturnedValueStateCallbackTy<NonNullStateTy> RVCallback =
+        [&](const ReturnedValueInfo *RVPtr) {
+          return checkValueForNonNullness(RVPtr->V, A, Dir, RVPtr->CtxI, Cache);
+        };
+    return A.forwardReturnedValues(State, F, RVCallback);
+  }
+
+  State.revertToKnown();
+  return CHANGED;
+}
+
+/// ------------------------ No-Alias Attributes ------------------------------
+
+/// A compound class for all no-alias attributes.
+struct AANoAliasImpl : public AANoAlias {
+
+  /// See AbstractAttribute::AbstractAttribute(...).
+  AANoAliasImpl(Value &V) : AANoAlias(V) {}
+
+  /// Return true if we know that the underlying value cannot alias with
+  /// anything (not based on it) in its respective scope.
+  bool isKnownNoAlias() const override { return State.getKnown(); }
+
+  /// Return true if we assume that the underlying value cannot alias with
+  /// anything (not based on it) in its respective scope. The direction @p Dir
+  /// decides if we look at the assumed information for forward or backward
+  /// traversal, or both, either inclusive or exclusive (see enum Direction).
+  bool isAssumedNoAlias() const override { return State.getAssumed(); }
+
+  /// See AbstractState::getState().
+  ///{
+  AbstractState &getState() override { return State; }
+  const AbstractState &getState() const override { return State; }
+  ///}
+
+protected:
+  /// Encapsulate the name of the underlying abstract state.
+  using NoAliasStateTy = BooleanState;
+  using NoAliasStateCache = StateCache<NoAliasStateTy>;
+
+  /// General helper function to determine if @p V is alias free in the
+  /// respective scope with regards to the deduction direction @p Dir.
+  NoAliasStateTy computeNoAliasState(Attributor &A, Value *V, Direction Dir,
+                                     NoAliasStateCache &Cache);
+
+  static NoAliasStateTy computeNoAliasStateForExactValue(Value *V,
+                                                         Attributor &A);
+
+  /// The underlying abstract state for all AANoAliasImpl classes.
+  NoAliasStateTy State;
+};
+
+AANoAliasImpl::NoAliasStateTy
+AANoAliasImpl::computeNoAliasState(Attributor &A, Value *V, Direction Dir,
+                                   NoAliasStateCache &Cache) {
+  if (Dir == BACKWARD)
+    return NoAliasStateTy::top();
+
+  return cachedPointerTraversal(Cache, V, computeNoAliasStateForExactValue, A);
+}
+
+AANoAliasImpl::NoAliasStateTy
+AANoAliasImpl::computeNoAliasStateForExactValue(Value *V, Attributor &A) {
+
+  if (auto *C = dyn_cast<Constant>(V)) {
+    if (C->isZeroValue() || isa<UndefValue>(V))
+      return NoAliasStateTy::bot();
+    return NoAliasStateTy::top();
+  }
+
+  if (isa<GlobalValue>(V))
+    return NoAliasStateTy::top();
+
+  // TODO: Use AANoCapture attributes.
+  if (PointerMayBeCaptured(V, /* ReturnCaptures */ false,
+                           /* StoreCaptures */ true))
+    return NoAliasStateTy::top();
+
+  auto *NoAliasAA = A.getAAFor<AANoAliasImpl>(*V);
+  if (NoAliasAA && NoAliasAA->isAssumedNoAlias()) {
+    if (!NoAliasAA->isKnownNoAlias())
+      /* register dependence */;
+    return NoAliasAA->State;
+  }
+
+  if (isNoAliasFn(V, /* TLI */ nullptr, /* LookThroughBitcasts */ true))
+    return NoAliasStateTy::bot();
+
+  return NoAliasStateTy::top();
+}
+
+/// ------------------------ No-Alias Arguments -------------------------------
+
+/// An AA to represent the no-alias function return attribute.
+struct AANoAliasArgument final : public AANoAliasImpl {
+
+  /// See AANoAliasImpl::AANoAliasImpl(...).
+  AANoAliasArgument(Argument &Arg) : AANoAliasImpl(Arg) {
+
+    // Determine if the IR already provides enough information.
+    if (Arg.hasAttribute(Attribute::NoAlias))
+      State.indicateFixpoint();
+  }
+
+  /// See the AbstractAttribute interface for information.
+  ///{
+
+  /// See AbstractAttribute::updateImpl(Attributor &A, Direction Dir).
+  virtual bool updateImpl(Attributor &A, Direction Dir) override;
+
+  /// See AbstractAttribute::getArgumentNo().
+  virtual int getArgumentNo() const override {
+    return cast<Argument>(getAnchoredValue()).getArgNo();
+  }
+
+  /// See AbstractAttribute::getManifestPosition().
+  virtual ManifestPosition getManifestPosition() const override {
+    return MP_ARGUMENT;
+  };
+
+  /// See AbstractAttribute::getStatisticObj().
+  virtual Statistic *getStatisticObj() const override {
+    return &NumFnArgumentNoAlias;
+  }
+
+  ///}
+};
+
+bool AANoAliasArgument::updateImpl(Attributor &A, Direction Dir) {
+  if (Dir == BACKWARD) {
+    State.revertToKnown();
+    return CHANGED;
+  }
+
+  Argument &Arg = cast<Argument>(getAnchoredValue());
+  Function &F = *Arg.getParent();
+  bool IsArgMemOnlyFn =
+      F.hasFnAttribute(Attribute::ArgMemOnly) ||
+      F.hasFnAttribute(Attribute::InaccessibleMemOrArgMemOnly);
+
+  // Callback function
+  CallSiteCallbackTy CallSiteCheck = [&](CallSite CS) {
+    assert(CS && "Sanity check: Call site was not initialized properly!");
+    Function &CSFn = *CS.getCaller();
+
+    Value *V = CS.getArgOperand(Arg.getArgNo());
+    V = V->stripInBoundsOffsets();
+
+    if (isa<GlobalValue>(V)) {
+      LLVM_DEBUG(errs() << "no-alias failed maybe captured (global!): " << *V
+                        << " in " << CSFn.getName() << "\n");
+      return false;
+    }
+
+    auto *NoAliasAA = A.getAAFor<AANoAliasImpl>(*V);
+    bool VisNoAlias = NoAliasAA && NoAliasAA->isAssumedNoAlias();
+
+    if (!IsArgMemOnlyFn && !VisNoAlias && !isIdentifiedFunctionLocal(V)) {
+      LLVM_DEBUG(errs() << "no-alias failed non-func-loc: " << *V << " in "
+                        << CSFn.getName() << "\n");
+      return false;
+    }
+
+    const DominatorTree &DT = A.getDT(CSFn);
+    Instruction *CSInst = CS.getInstruction();
+    if (PointerMayBeCapturedBefore(V, /* ReturnCaptures */ false,
+                                   /* StoreCaptures */ true, CSInst, &DT)) {
+      LLVM_DEBUG(errs() << "no-alias failed maybe captured: " << *V << " in "
+                        << CSFn.getName() << "\n");
+      return false;
+    }
+
+    AAResults &AAR = A.getAAR(CSFn);
+    for (Use &U : CS.args()) {
+      if (CS.getArgumentNo(&U) == Arg.getArgNo())
+        continue;
+      Value *ArgOp = U->stripInBoundsOffsets();
+      if (!AAR.alias(MemoryLocation(ArgOp), MemoryLocation(V)))
+        continue;
+      LLVM_DEBUG(errs() << "May alias: " << *U.get() << " : " << *V << " in "
+                        << CSFn.getName() << "\n");
+      return false;
+    }
+
+    if (VisNoAlias)
+      LLVM_DEBUG(errs() << "CS in " << CSFn.getName() << " is OK of " << Arg
+                        << "\n");
+    return true;
+  };
+
+  if (A.foreachCallSite(F, CallSiteCheck))
+    return UNCHANGED;
+
+  State.revertToKnown();
+  return CHANGED;
+}
+
+/// -------- Memory Behavior Attributes (write/read-only/none) ----------------
+
+/// A class to hold the state of for memory behaviour attributes.
+struct AAMemoryAccessBehaviorImpl : public AAMemoryAccessBehavior {
+
+  AAMemoryAccessBehaviorImpl(Value &V) : AAMemoryAccessBehavior(V) {
+  }
+
+  /// See AAMemoryAccessBehavior::isKnownReadNone();
+  bool isKnownReadNone() const override {
+    return getNoReadState().getKnown() && getNoWriteState().getKnown();
+  }
+
+  /// See AAMemoryAccessBehavior::isAssumedReadNone();
+  bool isAssumedReadNone() const override  {
+    return getNoReadState().getAssumed() && getNoWriteState().getAssumed();
+  }
+
+  /// See AAMemoryAccessBehavior::isKnownReadOnly();
+  bool isKnownReadOnly() const override  {
+    return getNoWriteState().getKnown();
+  }
+
+  /// See AAMemoryAccessBehavior::isAssumedReadOnly();
+  bool isAssumedReadOnly() const override  {
+    return getNoWriteState().getAssumed();
+  }
+
+  /// See AAMemoryAccessBehavior::isKnownWriteOnly();
+  bool isKnownWriteOnly() const override  {
+    return getNoReadState().getKnown();
+  }
+
+  /// See AAMemoryAccessBehavior::isAssumedWriteOnly();
+  bool isAssumedWriteOnly() const override  {
+    return getNoReadState().getAssumed();
+  }
+
+  /// See AbstractAttribute::getState()
+  ///{
+  AbstractState &getState() override { return State; }
+  const AbstractState &getState() const override { return State; }
+  ///}
+
+  // TODO!! Add may-read/write
+  /// See AbstractAttribute::useKnownAccessInformation(...).
+  //virtual void useKnownAccessInformation(uint64_t Length,
+                                         //const APInt &Offset) override;
+  BooleanState &getNoReadState() { return State.Left; }
+  const BooleanState &getNoReadState() const { return State.Left; }
+  BooleanState &getNoWriteState() { return State.Right; }
+  const BooleanState &getNoWriteState() const { return State.Right; }
+
+protected:
+
+  using StateTy = PairState<BooleanState, BooleanState>;
+  StateTy State;
+};
+
+/// An AA to represent the memory behavior function attributes.
+struct AAFunctionMemoryBehavior final : public AAMemoryAccessBehaviorImpl {
+
+  /// See AAMemoryAccessBehaviorImpl::AAMemoryAccessBehaviorImpl(...).
+  AAFunctionMemoryBehavior(Function &F, AAResults &AAR)
+      : AAMemoryAccessBehaviorImpl(F), AAR(AAR),
+        State(*this, AAMemoryAccessBehaviorImpl::getState()) {
+
+    auto ModRef = AAR.getModRefBehavior(&F);
+    if (AAResults::onlyReadsMemory(ModRef))
+      getNoWriteState().setKnown(true);
+    if (AAResults::doesNotReadMemory(ModRef))
+      getNoReadState().setKnown(true);
+
+    if (AAResults::onlyAccessesArgPointees(ModRef))
+      State.ArgMemOnly.setKnown(true);
+  }
+
+  void addMemoryAccessInst(Instruction &I) {
+    CallSite CS(&I);
+    if (CS)
+      State.AllCalls.push_back(&I);
+    else
+      State.AllMemInst.push_back(&I);
+    categorize(I);
+  }
+
+  /// See AAMemoryAccessBehavior::isKnownReadNone();
+  bool isKnownReadNone() const override {
+    return State.UnknownCalls.empty() && AAMemoryAccessBehaviorImpl::isKnownReadNone();
+  }
+
+  /// See AAMemoryAccessBehavior::isKnownReadOnly();
+  bool isKnownReadOnly() const override {
+    return State.UnknownCalls.empty() && AAMemoryAccessBehaviorImpl::isKnownReadOnly();
+  }
+
+  /// See AAMemoryAccessBehavior::isKnownWriteOnly();
+  bool isKnownWriteOnly() const override {
+    return State.UnknownCalls.empty() && AAMemoryAccessBehaviorImpl::isKnownWriteOnly();
+  }
+
+  virtual bool isKnownArgMemOnly() const override {
+    return State.UnknownCalls.empty() && State.ArgMemOnly.getKnown();
+  }
+
+  virtual bool isAssumedArgMemOnly() const override {
+    return State.ArgMemOnly.getAssumed();
+  }
+
+  /// See the AbstractAttribute interface for information.
+  ///{
+
+  /// See AbstractAttribute::updateImpl(Attributor &A, Direction Dir).
+  virtual bool updateImpl(Attributor &A, Direction Dir) override;
+
+  virtual bool manifest(Attributor &A) override;
+
+  /// See AbstractAttribute::getState()
+  ///{
+  AbstractState &getState() override { return State; }
+  const AbstractState &getState() const override { return State; }
+  ///}
+
+  /// See AbstractAttribute::getManifestPosition().
+  virtual ManifestPosition getManifestPosition() const override {
+    return MP_FUNCTION;
+  };
+
+  /// See AbstractAttribute::getStatisticObj().
+  virtual Statistic *getStatisticObj() const override {
+    return isAssumedReadNone()
+               ? &NumFnsReadNone
+               : (isAssumedReadOnly()
+                      ? &NumFnsReadOnly
+                      : (isAssumedWriteOnly() ? &NumFnsWriteOnly : nullptr));
+  }
+
+  ///}
+
+protected:
+
+  struct MemoryBehaviorState : public AbstractState {
+
+    MemoryBehaviorState(AAFunctionMemoryBehavior &MemAccBehImpl, AbstractState &Parent)
+        : MemAccBehImpl(MemAccBehImpl), Parent(Parent) {}
+
+    void resetAssumed() override {
+      Parent.resetAssumed();
+      ArgMemOnly.resetAssumed();
+
+      UnknownCalls = AllCalls;
+      for (Instruction *MemInst : AllMemInst)
+        MemAccBehImpl.categorize(*MemInst);
+    }
+
+    bool isWorstPossible() const override {
+      return Parent.isWorstPossible() && ArgMemOnly.isWorstPossible();
+    }
+
+    bool isBestPossible() const override {
+      return Parent.isBestPossible() && ArgMemOnly.isBestPossible() &&
+             UnknownCalls.empty();
+    }
+
+    void revertToKnown() override {
+      Parent.revertToKnown();
+      ArgMemOnly.revertToKnown();
+      UnknownCalls.clear();
+    }
+
+    bool isAtFixpoint() const override {
+      return Parent.isAtFixpoint() && ArgMemOnly.isAtFixpoint() &&
+             UnknownCalls.empty();
+    }
+
+    void indicateFixpoint() override {
+      Parent.indicateFixpoint();
+      ArgMemOnly.indicateFixpoint();
+      UnknownCalls.clear();
+    }
+
+    bool isConsistent() const override {
+      return Parent.isConsistent() && ArgMemOnly.isConsistent();
+    }
+
+    AAFunctionMemoryBehavior &MemAccBehImpl;
+    AbstractState &Parent;
+
+    BooleanState ArgMemOnly;
+
+    SmallVector<Instruction *, 64> AllCalls;
+    SmallVector<Instruction *, 64> AllMemInst;
+    SmallVector<Instruction *, 64> UnknownCalls;
+  };
+
+  friend class MemoryBehaviorState;
+
+  bool isIgnoredLocation(const MemoryLocation &Loc);
+  void categorize(Instruction &I);
+
+  AAResults &AAR;
+
+  using StateTy = MemoryBehaviorState;
+  StateTy State;
+};
+
+bool AAFunctionMemoryBehavior::isIgnoredLocation(const MemoryLocation &Loc) {
+  if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true)) {
+    errs() << *Loc.Ptr << " + [0:" << Loc.Size << "] is ignored!\n";
+    return true;
+  }
+
+  return false;
+}
+
+void AAFunctionMemoryBehavior::categorize(Instruction &I) {
+  CallSite CS(&I);
+  if (CS) {
+    State.UnknownCalls.push_back(&I);
+    return;
+  }
+
+  Value *Ptr = nullptr;
+  if (auto *LI = dyn_cast<LoadInst>(&I)) {
+    Ptr = LI->getPointerOperand()->stripInBoundsOffsets();
+    // Ignore non-volatile loads from local memory. (Atomic is okay here.)
+    if (!LI->isVolatile() && isIgnoredLocation(MemoryLocation(Ptr)))
+      return;
+  } else if (auto *SI = dyn_cast<StoreInst>(&I)) {
+    Ptr = SI->getPointerOperand()->stripInBoundsOffsets();
+    // Ignore non-volatile stores to local memory. (Atomic is okay here.)
+    if (!SI->isVolatile() && isIgnoredLocation(MemoryLocation(Ptr)))
+      return;
+  } else if (auto *VI = dyn_cast<VAArgInst>(&I)) {
+    Ptr = VI->getPointerOperand()->stripInBoundsOffsets();
+    // Ignore vaargs on local memory.
+    if (isIgnoredLocation(MemoryLocation(Ptr)))
+      return;
+  }
+
+  if (!Ptr || !isa<Argument>(Ptr))
+    State.ArgMemOnly.revertToKnown();
+
+  errs() << "I: " << I << "\n";
+  if (Ptr)
+    errs() << " PTr " << *Ptr <<"\n";
+  errs() << I.mayReadFromMemory() << " : " << I.mayWriteToMemory() << "\n";
+
+  if (I.mayReadFromMemory())
+    getNoReadState().revertToKnown();
+  if (I.mayWriteToMemory())
+    getNoWriteState().revertToKnown();
+}
+
+bool AAFunctionMemoryBehavior::updateImpl(Attributor &A, Direction Dir) {
+  if (Dir == FORWARD){
+    State.revertToKnown();
+    return CHANGED;
+  }
+
+  auto IsIgnoredUseValue = [&](const Use &U) {
+    Value *BasePtr = U.get()->stripInBoundsOffsets();
+    return isIgnoredLocation(MemoryLocation(BasePtr));
+  };
+  auto IsArgumentOrIgnoredUseValue = [&](const Use &U) {
+    Value *BasePtr = U.get()->stripInBoundsOffsets();
+    return isa<Argument>(BasePtr) || IsIgnoredUseValue(U);
+  };
+  auto ExtractCallSiteInfo = [&](CallSite CS, bool &MayRead,
+                                 bool &MayWrite, bool &MayNonArgMem) {
+    auto ModRef = AAR.getModRefBehavior(CS);
+    MayRead = !AAResults::doesNotReadMemory(ModRef);
+    MayWrite = !AAResults::onlyReadsMemory(ModRef);
+    MayNonArgMem = !AAResults::onlyAccessesArgPointees(ModRef);
+
+    if (!CS.getCalledFunction())
+      return;
+
+    auto *CalledFnAA =
+        A.getAAFor<AAFunctionMemoryBehavior>(*CS.getCalledFunction());
+    if (!CalledFnAA)
+      return;
+
+    if (CalledFnAA->isAssumedReadOnly())
+      MayWrite = false;
+    if (CalledFnAA->isAssumedWriteOnly())
+      MayRead = false;
+    if (CalledFnAA->isAssumedArgMemOnly())
+      MayNonArgMem = false;
+  };
+
+  bool Changed = UNCHANGED;
+  errs() << "UPDATE nr:" << getNoReadState() << " | nw:" << getNoWriteState()
+         << " | #c:" << State.UnknownCalls.size() << "\n";
+
+  for (Instruction *I : State.UnknownCalls) {
+    CallSite CS(I);
+    assert(CS);
+
+    if (CS.hasOperandBundles()) {
+      State.revertToKnown();
+      return CHANGED;
+    }
+
+    bool MayRead, MayWrite, MayNonArgMem;
+    ExtractCallSiteInfo(CS, MayRead, MayWrite, MayNonArgMem);
+    errs() << "CS: " << *I << " : " << MayRead << " : " << MayWrite << " : " << MayNonArgMem << "\n";
+
+    if (!MayNonArgMem &&
+        std::all_of(CS.arg_begin(), CS.arg_end(), IsIgnoredUseValue))
+      continue;
+
+    if (MayNonArgMem ||
+        !std::all_of(CS.arg_begin(), CS.arg_end(), IsArgumentOrIgnoredUseValue))
+      State.ArgMemOnly.revertToKnown();
+
+    if (MayRead)
+      getNoReadState().revertToKnown();
+    if (MayWrite)
+      getNoWriteState().revertToKnown();
+  }
+
+  return Changed;
+}
+
+bool AAFunctionMemoryBehavior::manifest(Attributor &A) {
+  if (getState().isWorstPossible())
+    return false;
+
+  Function &F = cast<Function>(getAnchoredValue());
+  if (isKnownReadNone()) {
+    F.removeFnAttr(Attribute::ReadOnly);
+    F.removeFnAttr(Attribute::WriteOnly);
+    F.removeFnAttr(Attribute::ArgMemOnly);
+    F.removeFnAttr(Attribute::InaccessibleMemOnly);
+    F.removeFnAttr(Attribute::InaccessibleMemOrArgMemOnly);
+
+    return AbstractAttribute::manifest(A);
+  }
+
+  bool Changed = false;
+  if (isKnownArgMemOnly() && !F.hasFnAttribute(Attribute::ArgMemOnly)) {
+    // TODO: Inacc
+    F.removeFnAttr(Attribute::InaccessibleMemOnly);
+    F.removeFnAttr(Attribute::InaccessibleMemOrArgMemOnly);
+    F.addFnAttr(Attribute::ArgMemOnly);
+    Changed = true;
+  }
+
+  if (isKnownReadOnly()) {
+    F.removeFnAttr(Attribute::WriteOnly);
+    return AbstractAttribute::manifest(A) || Changed;
+  }
+
+  if (isKnownWriteOnly()) {
+    F.removeFnAttr(Attribute::ReadOnly);
+    return AbstractAttribute::manifest(A) || Changed;
+  }
+
+  return Changed;
+}
+
+/// An AA to represent the memory behavior argument attributes.
+struct AAArgumentMemoryBehavior final : public AAMemoryAccessBehaviorImpl {
+
+  /// See AAMemoryAccessBehaviorImpl::AAMemoryAccessBehaviorImpl(...).
+  AAArgumentMemoryBehavior(Argument &Arg) : AAMemoryAccessBehaviorImpl(Arg) {
+    for (const Use &U : Arg.uses())
+      Uses.push_back(&U);
+    // TODO
+  }
+
+  /// See the AbstractAttribute interface for information.
+  ///{
+
+  /// See AbstractAttribute::updateImpl(Attributor &A, Direction Dir).
+  virtual bool updateImpl(Attributor &A, Direction Dir) override;
+
+  /// See AbstractAttribute::getManifestPosition().
+  virtual ManifestPosition getManifestPosition() const override {
+    return MP_ARGUMENT;
+  };
+
+  /// See AbstractAttribute::getStatisticObj().
+  virtual Statistic *getStatisticObj() const override {
+    return isAssumedReadNone()
+               ? &NumArgReadNone
+               : (isAssumedReadOnly()
+                      ? &NumArgReadOnly
+                      : (isAssumedWriteOnly() ? &NumArgWriteOnly : nullptr));
+  }
+
+  ///}
+
+private:
+
+  bool followUseIn(Attributor &A, const Use *U, Instruction *UserI);
+  bool analyzeUseIn(Attributor &A, const Use *U, Instruction *UserI);
+
+  SmallVector<const Use *, 32> Uses;
+
+};
+
+bool AAArgumentMemoryBehavior::followUseIn(Attributor &A, const Use *U, Instruction *UserI) {
+  switch (UserI->getOpcode()) {
+    case Instruction::Load: return false;
+
+    case Instruction::Call:
+    case Instruction::Invoke: {
+      CallSite CS(UserI);
+      if (!CS.isArgOperand(U) || !CS.getCalledFunction())
+        return true;
+      unsigned ArgNo = CS.getArgumentNo(U);
+      auto *ArgNoCaptureAA = A.getAAFor<AANoCapture>(
+          *(CS.getCalledFunction()->arg_begin() + ArgNo));
+      return !(ArgNoCaptureAA && ArgNoCaptureAA->isAssumedNoCapture());
+    }
+  }
+  return true;
+}
+
+bool AAArgumentMemoryBehavior::analyzeUseIn(Attributor &A, const Use *U,
+                                            Instruction *UserI) {
+  bool MayRead = false, MayWrite = false;
+  switch (UserI->getOpcode()) {
+  case Instruction::Load:
+    MayRead = true;
+    //MayWrite |= UserI->mayWriteToMemory();
+    break;
+  case Instruction::Store:
+    //MayRead |= UserI->mayReadFromMemory();
+    MayWrite |= cast<StoreInst>(UserI)->getPointerOperand() == U->get();
+    break;
+  case Instruction::Call:
+  case Instruction::Invoke: {
+    CallSite CS(UserI);
+    if (CS.isArgOperand(U) && CS.getCalledFunction()) {
+      unsigned ArgNo = CS.getArgumentNo(U);
+      auto *ArgMemAccBehavior = A.getAAFor<AAMemoryAccessBehavior>(
+          *(CS.getCalledFunction()->arg_begin() + ArgNo));
+      if (ArgMemAccBehavior) {
+        MayRead |= !(ArgMemAccBehavior->isAssumedReadOnly());
+        MayWrite |= !(ArgMemAccBehavior->isAssumedWriteOnly());
+        break;
+      }
+    }
+    LLVM_FALLTHROUGH;
+  }
+  default:
+    MayRead |= UserI->mayReadFromMemory();
+    MayWrite |= UserI->mayWriteToMemory();
+    break;
+  };
+
+  bool Changed = false;
+  if (MayRead && isAssumedWriteOnly()) {
+    getNoReadState().revertToKnown();
+    assert(!isAssumedWriteOnly());
+    Changed = true;
+  }
+  if (MayWrite && isAssumedReadOnly()) {
+    getNoWriteState().revertToKnown();
+    assert(!isAssumedReadOnly());
+    Changed = true;
+  }
+
+  return Changed;
+}
+
+bool AAArgumentMemoryBehavior::updateImpl(Attributor &A, Direction Dir) {
+  assert(isAssumedReadOnly() || isAssumedWriteOnly());
+
+  if (Dir == FORWARD) {
+    State.revertToKnown();
+    return CHANGED;
+  }
+
+  Argument &Arg = cast<Argument>(getAssociatedValue());
+  auto *FnMemBehavior = A.getAAFor<AAFunctionMemoryBehavior>(*Arg.getParent());
+  if (FnMemBehavior) {
+    if (FnMemBehavior->isAssumedReadNone()) {
+      assert(isAssumedReadNone());
+      return UNCHANGED;
+    }
+    if (!isAssumedWriteOnly() && FnMemBehavior->isAssumedReadOnly()) {
+      assert(isAssumedReadOnly());
+      return UNCHANGED;
+    }
+    if (!isAssumedReadOnly() && FnMemBehavior->isAssumedWriteOnly()) {
+      assert(isAssumedWriteOnly());
+      return UNCHANGED;
+    }
+  }
+
+  bool Changed = false;
+  for (int i = 0; i < Uses.size(); i++) {
+    const Use *U = Uses[i];
+    Instruction *UserI = cast<Instruction>(U->getUser());
+
+    if (followUseIn(A, U, UserI))
+      for (const Use &UserIUse : UserI->uses())
+        Uses.push_back(&UserIUse);
+
+    if (!UserI->mayReadOrWriteMemory())
+      continue;
+
+    Changed |= analyzeUseIn(A, U, UserI);
+  }
+
+  return Changed;
+}
+
+/// ---------------- No-Capture Attributes -----------------------
+
+/// A class to hold the state of for no-capture attributes.
+struct AANoCaptureImpl : public AANoCapture {
+
+  /// Constructor that takes the value this attribute is associated with (@p V)
+  /// as well as the function this attribute is related to.
+  AANoCaptureImpl(Value &V, Function &F) : AANoCapture(V) {
+    if (F.onlyReadsMemory() && F.doesNotThrow() &&
+        F.getReturnType()->isVoidTy())
+      State.indicateFixpoint();
+    if (V.getNumUses() == 0)
+      State.indicateFixpoint();
+  }
+
+  /// See AANoCapture::isKnownNoCapture().
+  bool isKnownNoCapture() const override { return State.getKnown(); }
+
+  /// See AANoCapture::isAssumedNoCapture(...).
+  bool isAssumedNoCapture() const override { return State.getAssumed(); }
+
+  /// See AbstractAttribute::getState()
+  ///{
+  AbstractState &getState() override { return State; }
+  const AbstractState &getState() const override { return State; }
+  ///}
+
+protected:
+
+  using StateTy = BooleanState;
+
+  StateTy State;
+};
+
+struct AACaptureUseTracker final : public CaptureTracker {
+
+  AACaptureUseTracker(Attributor &A) : A(A), AssumedNoCapture(true) {}
+
+  void tooManyUses() override { AssumedNoCapture = false; }
+
+  bool captured(const Use *U) override {
+    errs() << "Check use: " << *U->get() << " in " << *U->getUser() << "\n";
+    CallSite CS(U->getUser());
+    if (!CS || !CS.getCalledFunction() || !CS.isArgOperand(U)) {
+      AssumedNoCapture = false;
+      return true;
+    }
+
+    int ArgNo = CS.getArgumentNo(U);
+    auto *ArgNoCaptureAA =
+        A.getAAFor<AANoCapture>(*(CS.getCalledFunction()->arg_begin() + ArgNo));
+    errs() << *CS.getInstruction() << " @@@ " << ArgNo << " : " << ArgNoCaptureAA << "\n";
+    if (ArgNoCaptureAA)
+      errs( ) << *ArgNoCaptureAA << "\n";
+    if (ArgNoCaptureAA && ArgNoCaptureAA->isAssumedNoCapture())
+      return false;
+
+    AssumedNoCapture = false;
+    return true;
+  }
+
+  bool shouldExplore(const Use *U) override{
+    // TODO: "returned" and "no-capture" should be combinable in the future!
+    CallSite CS(U->get());
+    if (CS && !isa<IntrinsicInst>(CS.getInstruction()))
+      return false;
+    return true;
+  }
+
+  bool AssumedNoCapture;
+
+  Attributor &A;
+};
+
+/// An AA to represent the no-capture argument attribute.
+struct AANoCaptureArgument final : public AANoCaptureImpl {
+
+  /// See AANoCaptureImpl::AANoCaptureImpl(...).
+  AANoCaptureArgument(Argument &Arg) : AANoCaptureImpl(Arg, *Arg.getParent()) {
+    if (Arg.hasAttribute(getAttrKind()))
+      State.indicateFixpoint();
+  }
+
+  /// See the AbstractAttribute interface for information.
+  ///{
+
+  /// See AbstractAttribute::updateImpl(Attributor &A, Direction Dir).
+  virtual bool updateImpl(Attributor &A, Direction Dir) override;
+
+  /// See AbstractAttribute::getArgumentNo().
+  virtual int getArgumentNo() const override {
+    return cast<Argument>(getAnchoredValue()).getArgNo();
+  }
+
+  /// See AbstractAttribute::getManifestPosition().
+  virtual ManifestPosition getManifestPosition() const override {
+    return MP_ARGUMENT;
+  };
+
+  /// See AbstractAttribute::getStatisticObj().
+  virtual Statistic *getStatisticObj() const override {
+    return &NumFnArgumentNoCapture;
+  }
+
+  ///}
+};
+
+bool AANoCaptureArgument::updateImpl(Attributor &A, Direction Dir) {
+  if (Dir == FORWARD) {
+    State.revertToKnown();
+    return CHANGED;
+  }
+
+  // Functions that are readonly (or readnone) and nounwind and don't return
+  // a value can't capture arguments. Don't analyze them.
+  //if (F.onlyReadsMemory() && F.doesNotThrow() &&
+      //F.getReturnType()->isVoidTy()) {
+    //State.indicateFixpoint();
+    //return CHANGED;
+  //}
+
+  AACaptureUseTracker Tracker(A);
+  PointerMayBeCaptured(&getAssociatedValue(), &Tracker);
+  if (Tracker.AssumedNoCapture)
+    return UNCHANGED;
+
+  State.revertToKnown();
+  return CHANGED;
+}
+
+
+
+/// ---------------- Dereferenceable-Or-Null Attributes -----------------------
+
+/// A class to hold the state of for dereferenceable(-or-null) attributes.
+struct AADereferenceableOrNullImpl : public AADereferenceableOrNull {
+
+  /// Constructor that takes the value this attribute is associated with (@p V)
+  /// as well as the function this attribute is related to.
+  AADereferenceableOrNullImpl(Value &V, unsigned AddrSpace, Function &F)
+      : AADereferenceableOrNull(V), F(F),
+        NullPtrIsUndefined(!NullPointerIsDefined(&F, AddrSpace)) {}
+
+  /// See AADereferenceableOrNull::isKnownNonNull().
+  bool isKnownNonNull() const override { return State.getNonNull().getKnown(); }
+
+  /// See AADereferenceableOrNull::isAssumedNonNull(...).
+  bool isAssumedNonNull() const override {
+    return State.getNonNull().getAssumed();
+  }
+
+  /// See AADereferenceableOrNull::getKnownDereferenceableBytes().
+  uint64_t getKnownDereferenceableBytes() const override {
+    return State.getDerefBytes().getKnown();
+  }
+
+  /// See AADereferenceableOrNull::getAssumedDereferenceableBytes(...).
+  uint64_t getAssumedDereferenceableBytes() const override {
+    return State.getDerefBytes().getAssumed();
+  }
+
+  /// See AbstractAttribute::useKnownAccessInformation(...).
+  virtual void useKnownAccessInformation(uint64_t Length,
+                                         const APInt &Offset) override;
+
+  /// See AbstractAttribute::getState()
+  ///{
+  virtual AbstractState &getState() override { return State; }
+  virtual const AbstractState &getState() const override { return State; }
+  ///}
+
+  virtual bool isImpliedBy(AbstractAttribute &OtherAA, Direction Dir,
+                           bool &Changed) override;
+
+  using DerefBytesStateTy = IntegerState<uint64_t, 0, 0x40000000u>;
+  using NonNullStateTy = BooleanState;
+
+  struct DerefBytesOrNullStateTy
+      : public PairState<DerefBytesStateTy, NonNullStateTy> {
+    using Super = PairState<DerefBytesStateTy, NonNullStateTy>;
+
+    DerefBytesOrNullStateTy() : Super() {}
+    DerefBytesOrNullStateTy(const DerefBytesStateTy &DerefBytes,
+                            const NonNullStateTy &NonNull)
+        : Super(DerefBytes, NonNull) {}
+
+    DerefBytesStateTy &getDerefBytes() { return Left; }
+    const DerefBytesStateTy &getDerefBytes() const { return Left; }
+
+    NonNullStateTy &getNonNull() { return Right; }
+    const NonNullStateTy &getNonNull() const { return Right; }
+
+    virtual bool isWorstPossible() const override {
+      return getDerefBytes().isWorstPossible();
+    }
+
+    void combineStateWithOffset(const APInt &Offset, bool NullPtrIsUndefined) {
+      LLVM_DEBUG(errs() << "State: " << getDerefBytes() << " - Off: " << Offset
+                        << ":\n");
+      auto &DerefBytes = getDerefBytes();
+      if (DerefBytes.isWorstPossible())
+        return;
+
+      DerefBytes.setKnown(
+          std::max((int64_t)0,
+                   ((int64_t)DerefBytes.getKnown()) - Offset.getSExtValue()));
+      getNonNull().setKnown(NullPtrIsUndefined && DerefBytes.getKnown() > 0);
+
+      LLVM_DEBUG(errs() << "State: " << getDerefBytes() << " - Off: " << Offset
+                        << ":\n");
+
+      isConsistent();
+    }
+
+    static DerefBytesOrNullStateTy bot() {
+      return DerefBytesOrNullStateTy(DerefBytesStateTy::bot(),
+                                     NonNullStateTy::bot());
+    }
+    static DerefBytesOrNullStateTy top() {
+      return DerefBytesOrNullStateTy(DerefBytesStateTy::top(),
+                                     NonNullStateTy::top());
+    }
+  };
+
+  using DerefBytesOrNullStateCache = StateCache<DerefBytesOrNullStateTy>;
+
+protected:
+  /// Check the value @p V for dereferenceability and update the internal state
+  /// (IsAssumedNonNull and DerefBytes.Assumed). Returns true if the state was
+  /// altered.
+  DerefBytesOrNullStateTy
+  computeDerefOrNullStateTy(Value *V, Attributor &A, Direction Dir,
+                            DerefBytesOrNullStateCache &Cache);
+
+  static DerefBytesOrNullStateTy
+  computeDerefOrNullStateTyForExactValue(Value *V, Attributor &A, Direction Dir,
+                                         Function &F, bool NullPtrIsUndefined);
+
+  DerefBytesOrNullStateTy State;
+
+  const bool NullPtrIsUndefined;
+
+  /// The function associated with this abstract state.
+  Function &F;
+};
+
+void AADereferenceableOrNullImpl::useKnownAccessInformation(
+    uint64_t Length, const APInt &Offset) {
+  assert(Length);
+
+  DerefBytesStateTy DerefBytes(Length);
+  NonNullStateTy NonNull(NullPtrIsUndefined);
+
+  DerefBytesOrNullStateTy AccessState(DerefBytes, NonNull);
+
+  APInt AdjOffset(Offset);
+  AdjOffset.negate();
+  AccessState.combineStateWithOffset(AdjOffset, NullPtrIsUndefined);
+
+  State.getUpperBound(AccessState);
+}
+
+bool AADereferenceableOrNullImpl::isImpliedBy(AbstractAttribute &OtherAA,
+                                              Direction Dir, bool &Changed) {
+  Attribute::AttrKind OtherKind = OtherAA.getAttrKind();
+  assert(OtherKind == Attribute::Dereferenceable ||
+         OtherKind == Attribute::DereferenceableOrNull);
+
+  auto &OtherDerefOrNullAA =
+      static_cast<AADereferenceableOrNullImpl &>(OtherAA);
+  if (OtherDerefOrNullAA.getKnownDereferenceableBytes() == 0)
+    return false;
+
+  Value &Ptr = OtherAA.getAssociatedValue();
+  const DataLayout &DL = F.getParent()->getDataLayout();
+  unsigned IdxWidth =
+      DL.getIndexSizeInBits(Ptr.getType()->getPointerAddressSpace());
+  APInt Offset(IdxWidth, 0);
+  Value *Base = Ptr.stripAndAccumulateInBoundsConstantOffsets(DL, Offset);
+  if (Base != &getAssociatedValue())
+    return false;
+
+  auto OtherState = OtherDerefOrNullAA.State;
+  OtherState.combineStateWithOffset(Offset, NullPtrIsUndefined);
+  OtherState.revertToKnown();
+
+  auto OldState = State;
+  State.combine(OtherState);
+
+  Changed = (OldState != State);
+
+  // Try to improve the state and do not stop here.
+  return false;
+}
+
+AADereferenceableOrNullImpl::DerefBytesOrNullStateTy
+AADereferenceableOrNullImpl::computeDerefOrNullStateTy(
+    Value *V, Attributor &A, Direction Dir, DerefBytesOrNullStateCache &Cache) {
+  return cachedPointerTraversal(Cache, V,
+                                computeDerefOrNullStateTyForExactValue, A, Dir,
+                                F, NullPtrIsUndefined);
+}
+
+AADereferenceableOrNullImpl::DerefBytesOrNullStateTy
+AADereferenceableOrNullImpl::computeDerefOrNullStateTyForExactValue(
+    Value *Ptr, Attributor &A, Direction Dir, Function &F,
+    bool NullPtrIsUndefined) {
+
+  if (!Ptr->getType()->isPointerTy())
+    return DerefBytesOrNullStateTy::top();
+
+  const DataLayout &DL = F.getParent()->getDataLayout();
+
+  unsigned IdxWidth =
+      DL.getIndexSizeInBits(Ptr->getType()->getPointerAddressSpace());
+  APInt Offset(IdxWidth, 0);
+  Value *Base;
+  if (Dir == BACKWARD) {
+    Base = Ptr->stripAndAccumulateInBoundsConstantOffsets(DL, Offset);
+  } else {
+    Base = Ptr->stripPointerCasts();
+  }
+
+  // A "NULL" value is often defined as non-dereferenceable. If encountered we
+  // jump immediately to top.
+  if (isa<Constant>(Base) && cast<Constant>(Base)->isZeroValue() &&
+      NullPtrIsUndefined) {
+    return DerefBytesOrNullStateTy::top();
+  }
+
+  // Check if the value has an associated abstract attribute, e.g. an argument
+  // or call site. If that is the case, we can use the optimistic information,
+  // which should be the best possible information available, to update the
+  // current attribute.
+  auto *BaseDerefOrNullAA = A.getAAFor<AADereferenceableOrNullImpl>(*Base);
+  // errs() << "BAse: " << *Base << " : " << BaseDerefOrNullAA << "\n";
+  if (BaseDerefOrNullAA) {
+    // This attribute now depends on the abstract attribute for the value.
+    // addUsedAA(*BaseDerefOrNullAA);
+
+    DerefBytesOrNullStateTy BaseState = BaseDerefOrNullAA->State;
+    // errs() << BaseState << "\n";
+    BaseState.combineStateWithOffset(Offset, NullPtrIsUndefined);
+    // BaseState.revertToKnown();
+    // errs() << BaseState << "\n";
+    return BaseState;
+  }
+
+  bool BaseKnownCanBeNull = false;
+  if (uint64_t BaseKnownDerefBytes =
+          Base->getPointerDereferenceableBytes(DL, BaseKnownCanBeNull)) {
+    DerefBytesOrNullStateTy BaseState;
+    BaseState.getDerefBytes().setKnown(BaseKnownDerefBytes);
+    BaseState.getNonNull().setKnown(!BaseKnownCanBeNull);
+
+    BaseState.combineStateWithOffset(Offset, NullPtrIsUndefined);
+    BaseState.revertToKnown();
+
+    return BaseState;
+  }
+
+  if (isDereferenceablePointer(Base, DL)) {
+    uint64_t AccessSize =
+        DL.getTypeStoreSize(Base->getType()->getPointerElementType());
+    DerefBytesOrNullStateTy BaseState;
+    BaseState.getDerefBytes().setKnown(AccessSize);
+    BaseState.getNonNull().setKnown(NullPtrIsUndefined);
+
+    BaseState.combineStateWithOffset(Offset, NullPtrIsUndefined);
+    BaseState.revertToKnown();
+
+    return BaseState;
+  }
+
+  return DerefBytesOrNullStateTy::top();
+}
+
+raw_ostream &
+operator<<(raw_ostream &OS,
+           const AADereferenceableOrNullImpl::DerefBytesOrNullStateTy &State) {
+  return OS << "\tDereferenceable bytes " << State.getDerefBytes()
+            << ", non-null " << State.getNonNull();
+}
+
+/// An AA to represent the dereferenceable(-or-null) argument attribute.
+struct AADereferenceableOrNullArgument final
+    : public AADereferenceableOrNullImpl {
+
+  /// See AADereferenceableOrNullImpl::AADereferenceableOrNullImpl(...).
+  AADereferenceableOrNullArgument(Argument &Arg)
+      : AADereferenceableOrNullImpl(
+            Arg, Arg.getType()->getPointerAddressSpace(), *Arg.getParent()) {
+    uint64_t DerefBytes = Arg.getDereferenceableBytes();
+    if (DerefBytes)
+      State.getNonNull().setKnown(true);
+
+    uint64_t DerefOrNullBytes = Arg.getDereferenceableOrNullBytes();
+    State.getDerefBytes().setKnown(std::max(DerefBytes, DerefOrNullBytes));
+  }
+
+  /// See the AbstractAttribute interface for information.
+  ///{
+
+  /// See AbstractAttribute::updateImpl(Attributor &A, Direction Dir).
+  virtual bool updateImpl(Attributor &A, Direction Dir) override;
+
+  /// See AbstractAttribute::getArgumentNo().
+  virtual int getArgumentNo() const override {
+    return cast<Argument>(getAnchoredValue()).getArgNo();
+  }
+
+  /// See AbstractAttribute::getManifestPosition().
+  virtual ManifestPosition getManifestPosition() const override {
+    return MP_ARGUMENT;
+  };
+
+  /// See AbstractAttribute::getStatisticObj().
+  virtual Statistic *getStatisticObj() const override {
+    return isKnownNonNull() ? &NumFnArgumentDereferenceable
+                            : &NumFnArgumentDereferenceableOrNull;
+  }
+
+  ///}
+};
+
+bool AADereferenceableOrNullArgument::updateImpl(Attributor &A, Direction Dir) {
+  if (Dir == BACKWARD) {
+    State.revertToKnown();
+    return CHANGED;
+  }
+
+  DerefBytesOrNullStateTy UpdateState = DerefBytesOrNullStateTy::bot();
+
+  const DataLayout &DL = F.getParent()->getDataLayout();
+
+  DerefBytesOrNullStateCache Cache;
+  // Callback function
+  CallSiteCallbackTy CallSiteCheck = [&](CallSite CS) {
+    assert(CS && "Sanity check: Call site was not initialized properly!");
+
+    Value *Op = CS.getArgOperand(getArgumentNo());
+    DerefBytesOrNullStateTy OpState =
+        computeDerefOrNullStateTy(Op, A, Dir, Cache);
+    LLVM_DEBUG(dbgs() << "Operand: " << *Op << " at call site "
+                      << *CS.getInstruction() << " in "
+                      << CS.getCaller()->getName() << ":\n"
+                      << OpState << "\n";);
+    assert(OpState.isConsistent());
+
+    UpdateState.getLowerBound(OpState);
+    // errs() << "US: " << UpdateState << " OS: " << OpState << "\n";
+
+    return true;
+  };
+
+  // If no abstract argument was found look at the call sites.
+  if (A.foreachCallSite(F, CallSiteCheck)) {
+    // errs() << "fCS OK: " << UpdateState << "\n";
+    auto OldState = State;
+    State.combine(UpdateState);
+    return (State != OldState);
+  }
+
+  State.revertToKnown();
+  return CHANGED;
+}
+
+/// An AA to represent the dereferenceable(-or-null) argument attribute.
+struct AADereferenceableOrNullCallSiteArgument final
+    : public AADereferenceableOrNullImpl {
+
+  /// See AADereferenceableOrNullImpl::AADereferenceableOrNullImpl(...).
+  AADereferenceableOrNullCallSiteArgument(CallSite CS, unsigned ArgNo)
+      : AADereferenceableOrNullImpl(
+            *CS.getInstruction(),
+            CS.getArgOperand(ArgNo)->getType()->getPointerAddressSpace(),
+            *CS.getCaller()),
+        ArgNo(ArgNo) {
+
+    uint64_t DerefBytes = CS.getDereferenceableBytes(ArgNo);
+    if (DerefBytes)
+      State.getNonNull().setKnown(true);
+
+    uint64_t DerefOrNullBytes = CS.getDereferenceableOrNullBytes(ArgNo);
+    State.getDerefBytes().setKnown(std::max(DerefBytes, DerefOrNullBytes));
+  }
+
+  /// See the AbstractAttribute interface for information.
+  ///{
+
+  /// See AbstractAttribute::updateImpl(Attributor &A, Direction Dir).
+  virtual bool updateImpl(Attributor &A, Direction Dir) override;
+
+  /// See AbstractAttribute::getArgumentNo().
+  virtual int getArgumentNo() const override { return ArgNo; }
+
+  /// See AbstractAttribute::getManifestPosition().
+  virtual ManifestPosition getManifestPosition() const override {
+    // This attribute doesn't exist in IR so we won't manifest it.
+    return MP_CALL_SITE_ARGUMENT_NOT_IR;
+  };
+
+  /// See AbstractAttribute::getAssociatedValue().
+  ///{
+  Value &getAssociatedValue() override {
+    return *CallSite(&getAnchoredValue()).getArgOperand(getArgumentNo());
+  }
+  const Value &getAssociatedValue() const override {
+    return *ImmutableCallSite(&getAnchoredValue())
+                .getArgOperand(getArgumentNo());
+  }
+  ///}
+
+  /// See AbstractAttribute::getStatisticObj().
+  virtual Statistic *getStatisticObj() const override {
+    return isKnownNonNull() ? &NumCSArgumentDereferenceable
+                            : &NumCSArgumentDereferenceableOrNull;
+  }
+
+  ///}
+
+private:
+  /// The underlying value is the argument at position "ArgNo" of the call site
+  /// that is used as the underyling anchor. See
+  /// AbstractAttribute::getAssociatedValue().
+  const unsigned ArgNo;
+};
+
+bool AADereferenceableOrNullCallSiteArgument::updateImpl(Attributor &A,
+                                                         Direction Dir) {
+  CallSite CS(&getAnchoredValue());
+  Value *V = CS.getArgOperand(getArgumentNo());
+
+  if (Dir == BACKWARD) {
+    Function *Callee = CS.getCalledFunction();
+    assert(Callee && Callee->arg_size() > getArgumentNo());
+
+    Argument *FnArg = Callee->arg_begin() + getArgumentNo();
+    auto *DerefOrNullFnArgAA = A.getAAFor<AADereferenceableOrNullImpl>(*FnArg);
+    // errs() << "FnArg: " << *FnArg << " : " << DerefOrNullFnArgAA << "\n";
+
+    if (!DerefOrNullFnArgAA) {
+      State.revertToKnown();
+      return CHANGED;
+    }
+    // errs() << "FnArg: " << *FnArg << " : " << *DerefOrNullFnArgAA << "\n";
+
+    auto &ArgState =
+        static_cast<decltype(State) &>(DerefOrNullFnArgAA->getState());
+    if (State == ArgState)
+      return UNCHANGED;
+
+    State.combine(ArgState);
+    return CHANGED;
+  }
+
+  DerefBytesOrNullStateCache Cache;
+  DerefBytesOrNullStateTy UpdateState =
+      computeDerefOrNullStateTy(V, A, Dir, Cache);
+
+  auto OldState = State;
+  State.combine(UpdateState);
+  return !(State == OldState);
+}
+
+/// An AA to represent the dereferenceable(-or-null) function return attribute.
+struct AADereferenceableOrNullReturned final
+    : public AADereferenceableOrNullImpl {
+
+  /// See AADereferenceableOrNullImpl::AADereferenceableOrNullImpl(...).
+  AADereferenceableOrNullReturned(Function &F)
+      : AADereferenceableOrNullImpl(
+            F, F.getReturnType()->getPointerAddressSpace(), F) {}
+
+  /// See AbstractAttribute::updateImpl(Attributor &A, Direction Dir).
+  virtual bool updateImpl(Attributor &A, Direction Dir) override;
+
+  /// See AbstractAttribute::getManifestPosition().
+  virtual ManifestPosition getManifestPosition() const override {
+    return MP_RETURNED;
+  };
+
+  /// See AbstractAttribute::getStatisticObj().
+  virtual Statistic *getStatisticObj() const override {
+    return isKnownNonNull() ? &NumFnReturnDereferenceable
+                            : &NumFnReturnDereferenceableOrNull;
+  }
+};
+
+bool AADereferenceableOrNullReturned::updateImpl(Attributor &A, Direction Dir) {
+
+  if (Dir == FORWARD) {
+    DerefBytesOrNullStateCache Cache;
+    // Check all values returned by this function.
+    ReturnedValueStateCallbackTy<DerefBytesOrNullStateTy> RVCallback =
+        [&](const ReturnedValueInfo *RVPtr) {
+          return computeDerefOrNullStateTy(RVPtr->V, A, Dir, Cache);
+        };
+    return A.forwardReturnedValues(State, F, RVCallback);
+  }
+
+  State.revertToKnown();
+  return CHANGED;
+}
+
+/// --------------------- Function Return Values -------------------------------
+
+struct AAReturnedValuesImpl final : public AAReturnedValues {
+
+  /// See AbstractAttribute::AbstractAttribute(...).
+  AAReturnedValuesImpl(Function &F) : AAReturnedValues(F) {}
+
+  /// If this attribute is not top, we annotate the unique returned argument if
+  /// one exists.
+  virtual bool manifest(Attributor &A) override;
+
+  virtual AbstractState &getState() override { return State; }
+  virtual const AbstractState &getState() const override { return State; }
+
+  /// See AbstractAttribute::getManifestPosition().
+  virtual ManifestPosition getManifestPosition() const override {
+    // Unused, AbstractAttribute::manifest() is overwritten!
+    return MP_ARGUMENT;
+  };
+
+  /// See AbstractAttribute::getStatisticObj().
+  virtual Statistic *getStatisticObj() const override {
+    return &NumFnArgumentReturned;
+  }
+
+  /// See AbstractAttribute::updateImpl(Attributor &A, Direction Dir).
+  virtual bool updateImpl(Attributor &A, Direction Dir) override;
+
+  /// See AAReturnedValues::getNumReturnValues().
+  size_t getNumReturnValues() const override {
+    return State.ReturnedValues.size();
+  }
+
+  void setUniqueReturnedValue(Argument &Arg) {
+    assert(State.ReturnedValues.empty());
+    State.ReturnedValues.insert(new ReturnedValueInfo(&Arg));
+  }
+
+  /// Return the unique value returned by the associated function if one exists.
+  Value *getUniqueReturnedValue(Attributor &A) const override;
+
+  /// Iterators to walk through all possibly returned values.
+  ///{
+  iterator begin() override { return State.ReturnedValues.begin(); }
+  iterator end() override { return State.ReturnedValues.end(); }
+  ///}
+
+  /// Pretty print the attribute similar to the IR representation.
+  virtual const std::string getAsStr() const override;
+
+  /// Recursively collect potentially returned values, starting from
+  /// @p RV, into @p Container. While intermediate values are
+  /// also collected, this function walks through select/phi/casts.
+  bool collectReturnedValuesRecursively(Value *V, Instruction *CtxI,
+                                        const ReturnedValueInfo *RV);
+
+private:
+  struct ReturnedValuesStateTy final : public AbstractState {
+
+    ~ReturnedValuesStateTy() { DeleteContainerPointers(ReturnedValues); }
+
+    void resetAssumed() override {}
+
+    bool isWorstPossible() const override { return IsWorstPossible; }
+    bool isBestPossible() const override { return IsFixed; }
+
+    void revertToKnown() override { IsFixed = IsWorstPossible = true; }
+
+    bool isAtFixpoint() const override { return IsFixed; }
+
+    void indicateFixpoint() override { IsFixed = true; }
+
+    bool isConsistent() const override { return true; }
+
+    bool IsWorstPossible = false;
+    bool IsFixed = false;
+
+    /// The set of values potentially returned by the associated function.
+    ReturnedValuesTy ReturnedValues;
+    SmallPtrSet<Value *, 8> SeenValues;
+  };
+
+  ReturnedValuesStateTy State;
+};
+
+bool AAReturnedValuesImpl::manifest(Attributor &A) {
+  Value *UniqueReturn = getUniqueReturnedValue(A);
+  if (!UniqueReturn)
+    return false;
+
+  NumFnUniqueReturned++;
+
+  if (auto *C = dyn_cast<Constant>(UniqueReturn)) {
+    SmallVector<Use *, 8> Uses;
+    CallSiteCallbackTy CallSiteCheck = [&](CallSite CS) {
+      LLVM_DEBUG(dbgs() << "replace " << *CS.getInstruction()
+                        << " [#U: " << CS.getInstruction()->getNumUses()
+                        << " ] by " << *C << "\n";);
+      for (Use &U : CS.getInstruction()->uses())
+        if (isa<Instruction>(U.getUser()))
+          Uses.push_back(&U);
+      return true;
+    };
+    A.foreachCallSite(cast<Function>(getAnchoredValue()), CallSiteCheck, false);
+
+    for (Use *U : Uses) {
+      NumFnReturnedConstantsReplaced++;
+      U->set(C);
+    }
+    return false;
+  }
+
+  // If we have a unique return value _and_ it is an argument we
+  // annotate that argument as "returned".
+  if (auto *UniqueReturnArg = dyn_cast<Argument>(UniqueReturn)) {
+    if (UniqueReturnArg->hasAttribute(Attribute::Returned))
+      return false;
+
+    UniqueReturnArg->addAttr(Attribute::Returned);
+    NumFnArgumentReturned++;
+    return true;
+  }
+
+  return false;
+}
+
+/// Pretty print the attribute similar to the IR representation.
+const std::string AAReturnedValuesImpl::getAsStr() const {
+  return "returned(" +
+         (getState().isWorstPossible()
+              ? "inf"
+              : std::string("<= #") +
+                    std::to_string(State.ReturnedValues.size())) +
+         ")";
+};
+
+/// Recursively collect potentially returned values, starting from
+/// @p RV, into @p Container. While intermediate values are
+/// also collected, this function walks through select/phi/casts.
+bool AAReturnedValuesImpl::collectReturnedValuesRecursively(
+    Value *V, Instruction *CtxI, const ReturnedValueInfo *RV) {
+  bool CHANGED = false;
+  if (isa<UndefValue>(V))
+    return CHANGED;
+
+  // Collect the initial V just to see if we have seen it before.
+  if (!State.SeenValues.insert(V).second)
+    return CHANGED;
+
+  // Note that stripPointerCasts looks through functions with a returned
+  // arguments.
+  Value *StrippedRV = V->stripPointerCasts();
+  if (StrippedRV != V && !State.SeenValues.insert(StrippedRV).second)
+    return CHANGED;
+
+  // Look through select instructions.
+  if (auto *SI = dyn_cast<SelectInst>(StrippedRV)) {
+    CHANGED |= collectReturnedValuesRecursively(SI->getTrueValue(), CtxI, RV);
+    CHANGED |= collectReturnedValuesRecursively(SI->getFalseValue(), CtxI, RV);
+    return CHANGED;
+  }
+
+  // Look through phi nodes. Recursion is not a problem as we keep the PHI
+  // node in the container as well (see above).
+  if (auto *PHI = dyn_cast<PHINode>(StrippedRV)) {
+    for (int i = 0, e = PHI->getNumIncomingValues(); i < e; i++) {
+      BasicBlock *BB = PHI->getIncomingBlock(i);
+      Value *Op = PHI->getIncomingValue(i);
+      CHANGED |= collectReturnedValuesRecursively(Op, BB->getTerminator(), RV);
+    }
+    return CHANGED;
+  }
+
+  ReturnedValueInfo *NewRV = new ReturnedValueInfo(StrippedRV, CtxI, RV);
+  CHANGED |= State.ReturnedValues.insert(NewRV).second;
+  return CHANGED;
+}
+
+bool AAReturnedValuesImpl::updateImpl(Attributor &A, Direction Dir) {
+
+  // Check if we know of any values returned by the associated function, if not
+  // we are done.
+  if (getNumReturnValues() == 0) {
+    State.indicateFixpoint();
+    return UNCHANGED;
+  }
+
+  Function &F = cast<Function>(getAnchoredValue());
+  assert(F.hasExactDefinition());
+
+  SmallVector<ReturnedValueInfo, 16> NewReturnedValues;
+  SmallPtrSet<ReturnedValueInfo *, 4> ToBeRemovedRVs;
+
+  // Check if any of the returned values is a call instruction that we have to
+  // refine, thus it is a call of a function in this SCC.
+  ReturnedValueCallbackTy RVCallback = [&](const ReturnedValueInfo *RVPtr) {
+    const ReturnedValueInfo &RV = *RVPtr;
+    LLVM_DEBUG(errs() << "- " << RV << "\n");
+
+    CallSite ReturnedCallSite(RV.V);
+    if (!ReturnedCallSite)
+      return true;
+
+    Function *CalledFunction = ReturnedCallSite.getCalledFunction();
+    if (!CalledFunction)
+      return true;
+
+    // Iterate over the called function return values and determine if we can
+    // express them in the context of the call. If that works for all of them,
+    // the call is removed from the returned values and the values returned by
+    // the callee are used instead. If some values returned by the callee cannot
+    // be represented in the caller context, the call is kept and no values are
+    // added to the returned set.
+    SmallVector<ReturnedValueInfo, 16> NewCallReturnedValues;
+
+    Instruction *RVCallInst = ReturnedCallSite.getInstruction();
+    ReturnedValueCallbackTy InnerRVCallback =
+        [&](const ReturnedValueInfo *InnerRVPtr) {
+          const ReturnedValueInfo &InnerRV = *InnerRVPtr;
+          LLVM_DEBUG(errs() << "-- Inner" << InnerRV << "\n");
+
+          if (auto *CFMRVArg = dyn_cast<Argument>(InnerRV.V)) {
+            Value *ReturnedCallOperand =
+                ReturnedCallSite.getArgOperand(CFMRVArg->getArgNo());
+            NewCallReturnedValues.push_back(
+                ReturnedValueInfo(ReturnedCallOperand, RV.CtxI, &RV));
+            LLVM_DEBUG(errs()
+                       << "--- New" << NewCallReturnedValues.back() << "\n");
+            return true;
+          }
+
+          if (auto *C = dyn_cast<Constant>(InnerRV.V)) {
+            NewCallReturnedValues.push_back(
+                ReturnedValueInfo(C, RV.CtxI, &InnerRV));
+            LLVM_DEBUG(errs()
+                       << "--- New" << NewCallReturnedValues.back() << "\n");
+            return true;
+          }
+
+          CallSite InnerRVCallSite(InnerRV.V);
+          if (InnerRVCallSite && InnerRVCallSite.getCalledFunction() == &F) {
+            return true;
+          }
+
+          LLVM_DEBUG(errs() << "ARA updateImpl: leftover call RV: "
+                            << *InnerRV.V << "\n");
+          return false;
+        };
+
+    if (A.foreachReturnedValue(*CalledFunction, InnerRVCallback)) {
+      LLVM_DEBUG(errs() << "ARA updateImpl: remove call!\n");
+      ToBeRemovedRVs.insert(const_cast<ReturnedValueInfo *>(&RV));
+      NewReturnedValues.append(NewCallReturnedValues.begin(),
+                               NewCallReturnedValues.end());
+    }
+
+    return true;
+  };
+
+  bool Success = A.foreachReturnedValue(F, RVCallback);
+  assert(Success);
+
+  bool CHANGED = ToBeRemovedRVs.empty() ? UNCHANGED : CHANGED;
+
+  for (ReturnedValueInfo *RV : ToBeRemovedRVs)
+    State.ReturnedValues.erase(RV);
+
+  for (const ReturnedValueInfo &NewRV : NewReturnedValues) {
+    LLVM_DEBUG(errs() << "Collect new rvs rec: " << *NewRV.V << "\n");
+    if (collectReturnedValuesRecursively(NewRV.V, NewRV.CtxI, NewRV.RV))
+      CHANGED = CHANGED;
+  }
+
+  LLVM_DEBUG(errs() << "ARA updateImpl: CHANGED: " << CHANGED << "\n\n");
+
+  return CHANGED;
+}
+
+Value *AAReturnedValuesImpl::getUniqueReturnedValue(Attributor &A) const {
+  Value *UniqueReturnedValue = nullptr;
+
+  for (const ReturnedValueInfo *RV : State.ReturnedValues) {
+
+    // If we haven't determined a unique returned value, or it is equal to the
+    // current one, we remember the current one and continue.
+    if (!UniqueReturnedValue || UniqueReturnedValue == RV->V) {
+      UniqueReturnedValue = RV->V;
+      continue;
+    }
+
+    // We found a second value that could be returned and therefore conclude
+    // that there is no unique one.
+    LLVM_DEBUG(errs() << "No unique RV: " << *UniqueReturnedValue << " vs "
+                      << *RV->V << "\n");
+    return nullptr;
+  }
+
+  // If we never set a unique return value it means we never returned anything.
+  // In this case we can assume we return "undef".
+  // TODO: For the purpose of improving later analyses we could also mark the
+  // instruction after the call sites as unreachable!
+  if (!UniqueReturnedValue)
+    return UndefValue::get(cast<Function>(getAnchoredValue()).getReturnType());
+
+  Argument *UniqueReturnArg = dyn_cast<Argument>(UniqueReturnedValue);
+  if (!UniqueReturnArg)
+    return UniqueReturnedValue;
+
+  return UniqueReturnedValue;
+}
+
+/// --------------------- No-Alias function return ----------------------------
+
+/// An AA to represent the no-alias function return attribute.
+struct AANoAliasReturned final : public AANoAliasImpl {
+
+  /// See AANoAliasImpl::AANoAliasImpl(...).
+  AANoAliasReturned(Function &F) : AANoAliasImpl(F) {
+
+    // Determine if the IR already provides enough information.
+    if (F.hasAttribute(AttributeList::ReturnIndex, Attribute::NoAlias))
+      State.indicateFixpoint();
+  }
+
+  /// See the AbstractAttribute interface for information.
+  ///{
+
+  /// See AbstractAttribute::updateImpl(Attributor &A, Direction Dir).
+  virtual bool updateImpl(Attributor &A, Direction Dir) override;
+
+  /// See AbstractAttribute::getManifestPosition().
+  virtual ManifestPosition getManifestPosition() const override {
+    return MP_RETURNED;
+  };
+
+  /// See AbstractAttribute::getStatisticObj().
+  virtual Statistic *getStatisticObj() const override {
+    return &NumFnReturnNoAlias;
+  }
+
+  ///}
+};
+
+bool AANoAliasReturned::updateImpl(Attributor &A, Direction Dir) {
+  Function &F = cast<Function>(getAssociatedValue());
+
+  if (Dir == FORWARD) {
+    NoAliasStateCache Cache;
+    // Check all values returned by this function.
+    ReturnedValueStateCallbackTy<NoAliasStateTy> RVCallback =
+        [&](const ReturnedValueInfo *RVPtr) {
+          return computeNoAliasState(A, RVPtr->V, Dir, Cache);
+        };
+    return A.forwardReturnedValues(State, F, RVCallback);
+  }
+
+  State.revertToKnown();
+  return CHANGED;
+}
+
+/// -------------------------- Attributor -------------------------------------
+
+bool Attributor::run(Module &M) {
+  bool Changed = false;
+
+  for (Function &F : M) {
+
+    // TODO: We could always determine abstract attributes and if sufficient
+    // information was found we could duplicate the functions that do not have
+    // an exact definition.
+    if (!F.hasExactDefinition()) {
+
+      // Bookkeeping.
+      NumFnWithoutExactDefinition++;
+      continue;
+    }
+
+    if (F.hasFnAttribute(Attribute::Naked) ||
+        F.hasFnAttribute(Attribute::OptimizeNone))
+      continue;
+
+    // Bookkeeping.
+    NumFnWithExactDefinition++;
+
+    // Sanity check.
+    assert(!F.isDeclaration() && "Expected a definition not a declaration!");
+
+    Changed |= identifyAbstractAttributes(F);
+    Changed |= identifyExistingInformation(F);
+  }
+
+  AAVector AAWorklist, AAWorklistBuffer;
+
+  auto ScheduleDependentAAs = [&](AbstractAttribute *AA) {
+    // We iterate over all dependent abstract attributes.
+    const AASetVector &DependentAAs = AADependenceMap.lookup(AA);
+    for (AbstractAttribute *DependentAA : DependentAAs) {
+      const AbstractState &DependentAAState = DependentAA->getState();
+
+      // If the dependent attribute is already fixed there is no need to
+      // schedule it.
+      // if (DependentAAState.isAtFixpoint())
+      // continue;
+
+      // Since AA CHANGED and DependentAA depens on the information provided
+      // by AA we need to revisit DependentAA.
+      AAWorklist.push_back(DependentAA);
+    }
+  };
+
+  Direction Dir = BACKWARD, LastDir = FORWARD;
+  int Iterations = 0;
+  int Fixpoints = 0;
+  while (Fixpoints != 3) {
+    assert(Fixpoints >= 0 && Fixpoints <= 2);
+
+    LLVM_DEBUG(errs() << "\n\n[IT: " << Iterations << "] Start fixpoint in "
+                      << Dir << " with " << AAsInSCC.size() << "AAs:\n");
+
+    bool ChangedLast;
+    do {
+      ChangedLast = UNCHANGED;
+      for (AbstractAttribute *AA : AAsInSCC)
+        ChangedLast |= AA->update(*this, Dir);
+    } while (ChangedLast && (Iterations++ < MAX_ATTRIBUTOR_ITERATIONS_PER_LVL));
+
+    if (ChangedLast)
+      NumMaxIterationsPerLevelReached++;
+
+    bool ManifestChange = false;
+    for (AbstractAttribute *AA : AAsInSCC) {
+      AbstractState &AAState = AA->getState();
+
+      LLVM_DEBUG(errs() << "Attributor: PRE-FINAL: " << *AA << "\n");
+      ChangedLast ? AAState.revertToKnown() : AAState.indicateFixpoint();
+      LLVM_DEBUG(errs() << "Attributor: [" << ChangedLast << "] FINAL: " << *AA
+                        << "\n");
+      if (AAState.isWorstPossible())
+        continue;
+
+      bool LocalChange = AA->manifest(*this);
+      LLVM_DEBUG(errs() << "MANIFEST [" << LocalChange << "]: " << *AA << "\n");
+      ManifestChange |= LocalChange;
+    }
+
+    Changed |= ManifestChange;
+
+    Fixpoints++;
+    if (ManifestChange)
+      Fixpoints = 0;
+
+    if (Iterations >= MAX_ATTRIBUTOR_ITERATIONS_PER_LVL)
+      break;
+
+    std::swap(Dir, LastDir);
+
+    for (AbstractAttribute *AA : AAsInSCC) {
+      AA->getState().resetAssumed();
+    }
+  }
+
+  if (Iterations >= MAX_ATTRIBUTOR_ITERATIONS_PER_LVL) {
+    M.dump();
+    assert(0);
+  }
+
+  return Changed;
+}
+
+void Attributor::registerDependence(AbstractAttribute &From,
+                                    AbstractAttribute &To) {
+  LLVM_DEBUG(errs() << "-- DEP " << From << "\n   => " << To << "\n");
+  AADependenceMap[&To].insert(&From);
+}
+
+template <typename AAType>
+AAType *Attributor::getAAFor(const Value &V, int ArgNo,
+                             Attribute::AttrKind ID) {
+  assert(ID != Attribute::None && "TODO");
+  ImmutableCallSite CS(&V);
+  if (CS && ArgNo == -1 && CS.getCalledFunction())
+    return getAAFor<AAType>(*CS.getCalledFunction(), -1, ID);
+
+  if (auto *Arg = dyn_cast<Argument>(&V))
+    ArgNo = Arg->getArgNo();
+
+  const auto &KindToAbstractAttributeMap = AAMap.lookup({&V, ArgNo});
+  return static_cast<AAType *>(KindToAbstractAttributeMap.lookup(ID));
+}
+
+template <typename AAType>
+AAType &Attributor::registerAA(AAType &AA, AASetVector *LiveAAs) {
+  AAMap[{&AA.getAnchoredValue(), AA.getArgumentNo()}][AAType::ID] = &AA;
+  AAsInSCC.push_back(&AA);
+
+  if (LiveAAs) {
+    AA.registerPrecedingAndSucceedingAAs(*LiveAAs, /* Preceding */ true,
+                                         /* Succeeding */ true);
+    LiveAAs->insert(&AA);
+  }
+  return AA;
+}
+
+bool Attributor::foreachReturnedValue(Function &F,
+                                      ReturnedValueCallbackTy &Callback) {
+  auto *RVAA = getAAFor<AAReturnedValues>(F);
+  if (!RVAA)
+    return false;
+
+  if (RVAA->getState().isWorstPossible())
+    return false;
+
+  for (const ReturnedValueInfo *RV : *RVAA)
+    if (!Callback(RV))
+      return false;
+
+  return true;
+}
+
+template <typename StateTy>
+bool Attributor::forwardReturnedValues(
+    StateTy &State, Function &F,
+    ReturnedValueStateCallbackTy<StateTy> &Callback,
+    bool LookThroughRecursion) {
+
+  StateTy UpdateState = StateTy::bot();
+
+  // Check all values returned by this function.
+  ReturnedValueCallbackTy RVCallback = [&](const ReturnedValueInfo *RVPtr) {
+    // errs() << "RV: " << *RVPtr->V << " :: " << RVPtr->RV << "\n";
+
+    StateTy RVState = StateTy::top();
+    do {
+      if (!LookThroughRecursion && RVPtr->RV &&
+          RVPtr->RV->CtxI->getFunction() == &F)
+        return true;
+
+      RVState.getUpperBound(Callback(RVPtr));
+    } while (!RVState.isBestPossible() && (RVPtr = RVPtr->RV));
+
+    UpdateState.getLowerBound(RVState);
+    // errs() << "RVS: " << RVState << " US: "<<UpdateState << "\n";
+
+    return true;
+  };
+
+  if (!foreachReturnedValue(F, RVCallback)) {
+    LLVM_DEBUG(errs() << "fPRV failed for " << F.getName() << "\n");
+    State.revertToKnown();
+    return CHANGED;
+  }
+
+  if (UpdateState == State)
+    return UNCHANGED;
+
+  State.combine(UpdateState);
+  return CHANGED;
+}
+
+bool Attributor::foreachCallSite(Function &F, CallSiteCallbackTy &Callback,
+                                 bool RequireAllCallSites) {
+  // we can try to determine information from
+  // the call sites. However, this is only possible all call sites are known,
+  // hence the function has internal linkage.
+  if (RequireAllCallSites && !F.hasInternalLinkage()) {
+    LLVM_DEBUG(
+        dbgs()
+        << "Attributor: Function " << F.getName()
+        << " has no internal linkage, hence not all call sites are known\n");
+    return false;
+  }
+
+  for (const Use &U : F.uses()) {
+
+    CallSite CS(U.getUser());
+    if (!CS || !CS.isCallee(&U) || !CS.getCaller()->hasExactDefinition()) {
+      if (!RequireAllCallSites)
+        continue;
+
+      LLVM_DEBUG(dbgs() << "Attributor: User " << *U.getUser()
+                        << " is an invalid use of " << F.getName() << "\n");
+      return false;
+    }
+
+    assert(CS);
+    if (Callback(CS))
+      continue;
+
+    LLVM_DEBUG(dbgs() << "Attributor: Call site callback failed for "
+                      << *CS.getInstruction() << "\n");
+    return false;
+  }
+
+  return true;
+}
+
+template <typename StateTy>
+bool Attributor::forwardCallSiteStates(
+    StateTy &State, Function &F, CallSiteStateCallbackTy<StateTy> &Callback,
+    bool RequireAllCallSites) {
+#if 0
+
+  // we can try to determine information from
+  // the call sites. However, this is only possible all call sites are known,
+  // hence the function has internal linkage.
+  if (RequireAllCallSites && !F.hasInternalLinkage()) {
+    LLVM_DEBUG(
+        dbgs()
+        << "Attributor: Function " << F.getName()
+        << " hasn't internal linkage, hence call sites might be unknown\n");
+    return false;
+  }
+
+  for (const Use &U : F.uses()) {
+
+    CallSite CS(U.getUser());
+    if (!CS || !CS.isCallee(&U) || !CS.getCaller()->hasExactDefinition()) {
+      if (!RequireAllCallSites)
+        continue;
+
+      LLVM_DEBUG(dbgs() << "Attributor: User " << *U.getUser()
+                        << " is an invalid use of " << F.getName() << "\n");
+      return false;
+    }
+
+    assert(CS);
+    StateTy CSState = Callback(CS);
+
+
+    LLVM_DEBUG(dbgs() << "Attributor: Call site callback failed for "
+                      << *CS.getInstruction() << "\n");
+    return false;
+  }
+
+  return true;
+#endif
+  return false;
+}
+
+/// Determine opportunities to derive attributes.
+bool Attributor::identifyAbstractAttributes(Function &F) {
+  bool Changed = false;
+
+  auto &FunctionMemBehaviorAA = *new AAFunctionMemoryBehavior(F, getAAR(F));
+  registerAA(FunctionMemBehaviorAA);
+
+  // Return attributes are only appropriate if the return type is non void.
+  Type *ReturnType = F.getReturnType();
+  if (!ReturnType->isVoidTy()) {
+
+    if (ReturnType->isPointerTy()) {
+      // Return value attribute "no-alias".
+      registerAA(*new AANoAliasReturned(F));
+
+      // Return value attribute "dereferenceable(-or-null)".
+      registerAA(*new AADereferenceableOrNullReturned(F));
+
+      // TODO: Non-null should be a valid qualifier for integer types as
+      // well. Though, for now only pointer types are allowed.
+      // Return value attribute "non-null".
+      registerAA(*new AANonNullReturned(F));
+    }
+
+    // Argument attribute "returned" --- once per function.
+    registerAA(*new AAReturnedValuesImpl(F));
+  }
+
+  // TODO
+  DenseMap<BasicBlock *, AASetVector> LiveAAsMap;
+
+  BasicBlock *EntryBB = &F.getEntryBlock();
+  AASetVector &ArgumentAAs = LiveAAsMap[EntryBB];
+
+  // For each argument we check if we can derive attributes.
+  for (Argument &Arg : F.args()) {
+
+    // So far only pointer arguments are interesting. However, "returned"
+    // is also derived but as a "function return attribute" (see above).
+    if (!Arg.getType()->isPointerTy())
+      continue;
+
+    registerAA(*new AANoCaptureArgument(Arg), &ArgumentAAs);
+
+    registerAA(*new AAArgumentMemoryBehavior(Arg), &ArgumentAAs);
+
+    if (Arg.getNumUses() == 0)
+      continue;
+
+    // Argument attribute "dereferenceable(-or-null)".
+    auto &DerefOrNullAA = registerAA<AADereferenceableOrNullArgument>(
+        *new AADereferenceableOrNullArgument(Arg), &ArgumentAAs);
+
+    // Argument attribute "non-null".
+    auto &NonNullAA = registerAA<AANonNullArgument>(*new AANonNullArgument(Arg),
+                                                    &ArgumentAAs);
+    NonNullAA.PrecedingAAs.insert(&DerefOrNullAA);
+
+    // Return value attribute "no-alias".
+    registerAA(*new AANoAliasArgument(Arg), &ArgumentAAs);
+  }
+
+  ReversePostOrderTraversal<Function *> RPOT(&F);
+
+  for (BasicBlock *BB : RPOT) {
+    AASetVector &LiveAAs = LiveAAsMap[BB];
+
+    bool UniquePred = true;
+    BasicBlock *UniquePredBB = nullptr;
+    SmallVector<const AASetVector *, 4> PredLiveAAsWithBBAsUniqueSuccVec;
+    for (BasicBlock *PredBB : predecessors(BB)) {
+      UniquePred &= (!UniquePredBB || UniquePredBB == PredBB);
+      UniquePredBB = PredBB;
+
+      if (PredBB->getUniqueSuccessor() != BB)
+        continue;
+
+      if (!LiveAAsMap.count(PredBB))
+        continue;
+
+      PredLiveAAsWithBBAsUniqueSuccVec.push_back(&LiveAAsMap[PredBB]);
+    }
+
+    const AASetVector &UniquePredLiveAAs =
+        LiveAAsMap.lookup(UniquePred ? UniquePredBB : nullptr);
+    assert(UniquePred || UniquePredLiveAAs.empty());
+
+    auto RegisterLivePredAndSuccAAs = [&](AbstractAttribute &AA) {
+      AA.registerPrecedingAndSucceedingAAs(
+          UniquePredLiveAAs, /* Preceding */ true, /* Succeeding */ false);
+
+      for (const AASetVector *PredLiveAAsWithBBAsUniqueSucc :
+           PredLiveAAsWithBBAsUniqueSuccVec)
+        AA.registerPrecedingAndSucceedingAAs(*PredLiveAAsWithBBAsUniqueSucc,
+                                             /* Preceding */ false,
+                                             /* Succeeding */ true);
+    };
+
+    for (Instruction &I : *BB) {
+      LLVM_DEBUG(errs() << "      Visit: " << I << " [#LAAs: " << LiveAAs.size()
+                        << "]\n");
+
+      if (I.mayReadOrWriteMemory())
+        FunctionMemBehaviorAA.addMemoryAccessInst(I);
+
+      if (LoadInst *Load = dyn_cast<LoadInst>(&I)) {
+        if (Load->getType()->isPointerTy()) {
+          auto &AA = registerAA(*new AANonNullLoadResult(*Load), &LiveAAs);
+          RegisterLivePredAndSuccAAs(AA);
+        }
+      } else {
+        CallSite CS(&I);
+        if (CS && CS.getCalledFunction()) {
+          for (int i = 0, e = CS.getCalledFunction()->arg_size(); i < e; i++) {
+            if (!CS.getArgument(i)->getType()->isPointerTy())
+              continue;
+
+            {
+              // Call site argument attribute "dereferenceable-or-null".
+              auto &AA = registerAA(
+                  *new AADereferenceableOrNullCallSiteArgument(CS, i),
+                  &LiveAAs);
+              RegisterLivePredAndSuccAAs(AA);
+            }
+
+            {
+              // Call site argument attribute "non-null".
+              auto &AA =
+                  registerAA(*new AANonNullCallSiteArgument(CS, i), &LiveAAs);
+              RegisterLivePredAndSuccAAs(AA);
+            }
+          }
+        }
+      }
+
+      tryToUseInstruction(I, LiveAAs);
+
+      if (!isGuaranteedToTransferExecutionToSuccessor(&I))
+        LiveAAs.clear();
+    }
+
+    if (LiveAAs.empty())
+      continue;
+
+    if (BasicBlock *UniqSuccBB = BB->getUniqueSuccessor()) {
+      // AASetVector &SuccAAs = LiveAAsMap[UniqSuccBB];
+      // AASetVector &LiveAAs = LiveAAsMap[BB];
+      // SuccAAs.insert(LiveAAs.begin(), LiveAAs.end());
+    }
+  }
+
+  return Changed;
+}
+
+void Attributor::tryToUseCallSite(CallSite CS, AASetVector &InFlightAAs) {
+
+  Instruction *CSInst = CS.getInstruction();
+  LLVM_DEBUG(dbgs() << "Try to use CS [" << *CSInst << "]\n");
+
+  for (Use &ArgUse : CS.args()) {
+    const auto &CSArgK2AAMap =
+        AAMap.lookup({CSInst, CS.getArgumentNo(&ArgUse)});
+    LLVM_DEBUG({
+      dbgs() << " - Got " << CSArgK2AAMap.size() << " AAs for arg ["
+             << *ArgUse.get() << "]\n";
+      for (const auto &It : CSArgK2AAMap)
+        dbgs() << "  - " << It.first << " :" << *It.getSecond() << "\n";
+    });
+
+    if (CSArgK2AAMap.empty())
+      continue;
+
+    Value *ArgBase = ArgUse->stripInBoundsConstantOffsets();
+    const auto &BaseK2AAMap = AAMap.lookup({ArgBase, -1});
+    LLVM_DEBUG(dbgs() << " - Base is [" << *ArgBase << "]\n with "
+                      << BaseK2AAMap.size() << " AAs\n");
+
+    for (const auto &It : BaseK2AAMap) {
+      AbstractAttribute *AA = It.getSecond();
+
+      if (!InFlightAAs.count(AA))
+        continue;
+
+      // if (!EnableNonnullArgPropagation &&
+      // AA->getAttrKind() == Attribute::NonNull)
+      // continue;
+
+      // AbstractAttribute *CSAA = CSArgK2AAMap.lookup(AA->getAttrKind());
+      // if (!CSAA)
+      // continue;
+
+      // AA->addSufficientAA(*CSAA);
+      // CSAA->addSufficientAA(*AA);
+    }
+  }
+}
+
+void Attributor::tryToUseInstruction(Instruction &I, AASetVector &InFlightAAs) {
+  Function &F = *I.getFunction();
+  const DataLayout &DL = F.getParent()->getDataLayout();
+
+  auto UseAccess = [&](Value *Ptr, Value *LengthVal) {
+    uint64_t Length = 0;
+
+    if (!LengthVal) {
+      assert(Ptr->getType()->isSized() &&
+             "Sanity Check: Access to unsized pointer found!");
+      Length = DL.getTypeStoreSize(Ptr->getType()->getPointerElementType());
+    } else if (ConstantInt *CI = dyn_cast_or_null<ConstantInt>(LengthVal)) {
+      Length = CI->getZExtValue();
+    } else if (isKnownNonZero(LengthVal, DL)) {
+      Length = 1;
+    }
+
+    // If no length was determined we are unsure if there is an access at all.
+    if (!Length)
+      return;
+
+    unsigned IdxWidth =
+        DL.getIndexSizeInBits(Ptr->getType()->getPointerAddressSpace());
+    APInt Offset(IdxWidth, 0);
+    Ptr = Ptr->stripAndAccumulateInBoundsConstantOffsets(DL, Offset);
+    // Offset.negate();
+
+    int ArgNo = -1;
+    if (auto *Arg = dyn_cast<Argument>(Ptr))
+      ArgNo = Arg->getArgNo();
+
+    const auto &PtrK2AAMap = AAMap.lookup({Ptr, ArgNo});
+    LLVM_DEBUG(errs() << "Ptr " << *Ptr << ", length: " << Length
+                      << ", offset: " << Offset
+                      << " #AssAAs: " << PtrK2AAMap.size() << "\n");
+
+    for (const auto &It : PtrK2AAMap) {
+      AbstractAttribute *AA = It.getSecond();
+      LLVM_DEBUG(errs() << "Associated AA: " << *AA << "\n");
+
+      if (!InFlightAAs.count(AA))
+        continue;
+
+      AA->useKnownAccessInformation(Length, Offset);
+    }
+  };
+
+  if (auto *LI = dyn_cast<LoadInst>(&I)) {
+    if (!LI->isVolatile())
+      UseAccess(LI->getPointerOperand(), nullptr);
+    return;
+  }
+  if (auto *SI = dyn_cast<StoreInst>(&I)) {
+    if (!SI->isVolatile())
+      UseAccess(SI->getPointerOperand(), nullptr);
+    return;
+  }
+
+  if (auto *MI = dyn_cast<MemIntrinsic>(&I)) {
+    if (!MI->isVolatile()) {
+      UseAccess(MI->getDest(), MI->getLength());
+      if (auto *MTI = dyn_cast<MemTransferInst>(&I))
+        UseAccess(MTI->getSource(), MI->getLength());
+    }
+    return;
+  }
+
+  // CallSite CS(&I);
+  // if (CS)
+  // tryToUseCallSite(CS, InFlightAAs);
+}
+
+bool Attributor::identifyExistingInformation(Function &F) {
+  auto *ReturnedValuesAA = getAAFor<AAReturnedValuesImpl>(F);
+
+  if (ReturnedValuesAA) {
+    // There is nothing to do if an argument is already marked as
+    // 'returned' so we first check them.
+    for (Argument &Arg : F.args())
+      if (Arg.hasReturnedAttr())
+        ReturnedValuesAA->setUniqueReturnedValue(Arg);
+
+    // If no "returned" argument was present we check all blocks for return
+    // instructions and add the returned values, and potentially their
+    // operands, to the set of potentially returned values. Also see
+    // AAReturnedValuesImpl::collectReturnedValuesRecursively(...).
+    if (!ReturnedValuesAA->getNumReturnValues()) {
+      for (BasicBlock &BB : F)
+        if (auto *RI = dyn_cast<ReturnInst>(BB.getTerminator()))
+          ReturnedValuesAA->collectReturnedValuesRecursively(
+              RI->getReturnValue(), RI, nullptr);
+    }
+
+    auto MightChange = [&](const ReturnedValueInfo *RV) {
+      CallSite CS(RV->V);
+      if (CS && CS.getCalledFunction() &&
+          CS.getCalledFunction()->hasExactDefinition())
+        return true;
+      return false;
+    };
+
+    if (std::any_of(ReturnedValuesAA->begin(), ReturnedValuesAA->end(),
+                    MightChange))
+      return false;
+
+    // Fix the result so we know it will never change.
+    ReturnedValuesAA->getState().indicateFixpoint();
+    return ReturnedValuesAA->manifest(*this);
+  }
+
+  return false;
+}
+
 /// Returns the memory access attribute for function F using AAR for AA results,
 /// where SCCNodes is the current SCC.
 ///
 /// If ThisBody is true, this function may examine the function body and will
 /// return a result pertaining to this copy of the function. If it is false, the
 /// result will be based only on AA results for the function declaration; it
 /// will be assumed that some other (perhaps less optimized) version of the
 /// function may be selected at link time.
if (CS) {
         if (isModSet(MRI))
           // Writes non-local memory.
           WritesMemory = true;
         if (isRefSet(MRI))
           // Ok, it reads non-local memory.
           ReadsMemory = true;
       }
       continue;
-    } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
+    } else if (auto *LI = dyn_cast<LoadInst>(I)) {
       // Ignore non-volatile loads from local memory. (Atomic is okay here.)
       if (!LI->isVolatile()) {
         MemoryLocation Loc = MemoryLocation::get(LI);
         if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
           continue;
       }
-    } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
+    } else if (auto *SI = dyn_cast<StoreInst>(I)) {
       // Ignore non-volatile stores to local memory. (Atomic is okay here.)
       if (!SI->isVolatile()) {
         MemoryLocation Loc = MemoryLocation::get(SI);
         if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
           continue;
       }
-    } else if (VAArgInst *VI = dyn_cast<VAArgInst>(I)) {
+    } else if (auto *VI = dyn_cast<VAArgInst>(I)) {
       // Ignore vaargs on local memory.
       MemoryLocation Loc = MemoryLocation::get(VI);
       if (AAR.pointsToConstantMemory(Loc, /*OrLocal=*/true))
         continue;
     }
 
     // Any remaining instructions need to be taken seriously!  Check if they
     // read or write memory.
static bool addReadAttrs(const SCCNodeSet &SCCNodes, AARGetterT &&AARGetter) {
   bool WritesMemory = false;
   for (Function *F : SCCNodes) {
     // Call the callable parameter to look up AA results for this function.
     AAResults &AAR = AARGetter(*F);
 
     // Non-exact function definitions may not be selected at link time, and an
     // alternative version that writes to memory may be selected.  See the
     // comment on GlobalValue::isDefinitionExact for more details.
-    switch (checkFunctionMemoryAccess(*F, F->hasExactDefinition(),
-                                      AAR, SCCNodes)) {
+    switch (
+        checkFunctionMemoryAccess(*F, F->hasExactDefinition(), AAR, SCCNodes)) {
     case MAK_MayWrite:
       return false;
     case MAK_ReadOnly:
       ReadsMemory = true;
       break;
     case MAK_WriteOnly:
       WritesMemory = true;
       break;
     case MAK_ReadNone:
       // Nothing to do!
       break;
     }
   }
 
   // Success!  Functions in this SCC do not access memory, or only read memory.
   // Give them the appropriate attribute.
   bool MadeChange = false;
 
   assert(!(ReadsMemory && WritesMemory) &&
-          "Function marked read-only and write-only");
   for (Function *F : SCCNodes) {
     if (F->doesNotAccessMemory())
       // Already perfect!
       continue;
 
     if (F->onlyReadsMemory() && ReadsMemory)
       // No change.
       continue;
 
     if (F->doesNotReadMemory() && WritesMemory)
       continue;
 
     MadeChange = true;
 
+    errs() << "Write: " << WritesMemory << " Reads: " << ReadsMemory << "\n";
+    F->dump();
+
     // Clear out any existing attributes.
     F->removeFnAttr(Attribute::ReadOnly);
     F->removeFnAttr(Attribute::ReadNone);
     F->removeFnAttr(Attribute::WriteOnly);
 
     if (!WritesMemory && !ReadsMemory) {
       // Clear out any "access range attributes" if readnone was deduced.
       F->removeFnAttr(Attribute::ArgMemOnly);
       F->removeFnAttr(Attribute::InaccessibleMemOnly);
       F->removeFnAttr(Attribute::InaccessibleMemOrArgMemOnly);
     }
 
     // Add in the new attribute.
     if (WritesMemory && !ReadsMemory)
       F->addFnAttr(Attribute::WriteOnly);
     else
       F->addFnAttr(ReadsMemory ? Attribute::ReadOnly : Attribute::ReadNone);
 
+
     if (WritesMemory && !ReadsMemory)
       ++NumWriteOnly;
     else if (ReadsMemory)
       ++NumReadOnly;
     else
       ++NumReadNone;
   }
 
+  assert(!MadeChange);
   return MadeChange;
 }
 
 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.
while (!Worklist.empty()) {
     default:
       return Attribute::None;
     }
   }
 
   return IsRead ? Attribute::ReadOnly : Attribute::ReadNone;
 }
 
-/// Deduce returned attributes for the SCC.
 static bool addArgumentReturnedAttrs(const SCCNodeSet &SCCNodes) {
-  bool Changed = false;
+  bool CHANGED = false;
+
+  // Check each function in turn, determining if an argument is always returned.
+  for (Function *F : SCCNodes) {
+    // We can infer and propagate function attributes only when we know that the
+    // definition we'll get at link time is *exactly* the definition we see now.
+    // For more details, see GlobalValue::mayBeDerefined.
+    if (!F->hasExactDefinition())
+      continue;
+
+    if (F->getReturnType()->isVoidTy())
+      continue;
+
+    // There is nothing to do if an argument is already marked as 'returned'.
+    if (llvm::any_of(F->args(),
+                     [](const Argument &Arg) { return Arg.hasReturnedAttr(); }))
+      continue;
+
+    auto FindRetArg = [&]() -> Value * {
+      Value *RetArg = nullptr;
+      for (BasicBlock &BB : *F)
+        if (auto *Ret = dyn_cast<ReturnInst>(BB.getTerminator())) {
+          // Note that stripPointerCasts should look through functions with
+          // returned arguments.
+          Value *RetVal = Ret->getReturnValue()->stripPointerCasts();
+          if (!isa<Argument>(RetVal) || RetVal->getType() != F->getReturnType())
+            return nullptr;
+
+          if (!RetArg)
+            RetArg = RetVal;
+          else if (RetArg != RetVal)
+            return nullptr;
+        }
+
+      return RetArg;
+    };
+
+    if (Value *RetArg = FindRetArg()) {
+      auto *A = cast<Argument>(RetArg);
+      A->addAttr(Attribute::Returned);
+      ++NumReturned;
+      CHANGED = true;
+      F->dump();
+    }
+  }
+
+  assert(!CHANGED);
+  return CHANGED;
+}
+
+/// Deduce returned attributes for the SCC.
+static bool addArgumentReturnedAttrs2(const SCCNodeSet &SCCNodes) {
+  bool CHANGED = false;
 
   struct ReturnValueInfoTy {
     Value *ReturnValue;
     SmallPtrSet<CallInst *, 4> CallReturnValues;
   };
 
   DenseMap<Function *, ReturnValueInfoTy> FunctionReturnValueInfo;
 
for (Function *F : SCCNodes) {
 
         RVI.ReturnValue = nullptr;
         RVI.CallReturnValues.clear();
         break;
       }
     }
   } while (!AllFunctionsAreFixed);
 
-
   for (Function *F : SCCNodes) {
 
     auto &RVI = FunctionReturnValueInfo[F];
     if (!RVI.ReturnValue)
       continue;
 
-    NumReturnedKnown++;
-    NumReturnedKnownWithCalls += !RVI.CallReturnValues.empty();
-
     if (Argument *Arg = dyn_cast<Argument>(RVI.ReturnValue)) {
+      if (Arg->hasReturnedAttr())
+        continue;
+
       Arg->addAttr(Attribute::Returned);
-      NumReturned++;
-      NumReturnedWithCalls += !RVI.CallReturnValues.empty();
-      Changed = true;
+      CHANGED = true;
     } else if (isa<Constant>(RVI.ReturnValue)) {
-      NumReturnedConstantKnown++;
-      NumReturnedConstantWithCalls += !RVI.CallReturnValues.empty();
-      //errs() << "Found returned value is " << *RVI.ReturnValue
-             //<< " [#RetCalls: " << RVI.CallReturnValues.size() << "]\n";
+      // errs() << "Found returned value is " << *RVI.ReturnValue
     } else {
-      //errs() << "Found returned value is " << *RVI.ReturnValue
-             //<< " [#RetCalls: " << RVI.CallReturnValues.size() << "]\n";
+      // errs() << "Found returned value is " << *RVI.ReturnValue
     }
   }
 
-  return Changed;
+  assert(!CHANGED);
+  return CHANGED;
 }
 
 /// If a callsite has arguments that are also arguments to the parent function,
 /// try to propagate attributes from the callsite's arguments to the parent's
 /// arguments. This may be important because inlining can cause information loss
 /// when attribute knowledge disappears with the inlined call.
 static bool addArgumentAttrsFromCallsites(Function &F) {
   if (!EnableNonnullArgPropagation)
     return false;
 
-  bool Changed = false;
+  bool CHANGED = false;
 
   // For an argument attribute to transfer from a callsite to the parent, the
   // call must be guaranteed to execute every time the parent is called.
   // Conservatively, just check for calls in the entry block that are guaranteed
   // to execute.
   // TODO: This could be enhanced by testing if the callsite post-dominates the
   // entry block or by doing simple forward walks or backward walks to the
   // callsite.
   BasicBlock &Entry = F.getEntryBlock();
   for (Instruction &I : Entry) {
     if (auto CS = CallSite(&I)) {
       if (auto *CalledFunc = CS.getCalledFunction()) {
         for (auto &CSArg : CalledFunc->args()) {
           if (!CSArg.hasNonNullAttr())
             continue;
 
           // If the non-null callsite argument operand is an argument to 'F'
           // (the caller) and the call is guaranteed to execute, then the value
           // must be non-null throughout 'F'.
           auto *FArg = dyn_cast<Argument>(CS.getArgOperand(CSArg.getArgNo()));
           if (FArg && !FArg->hasNonNullAttr()) {
             FArg->addAttr(Attribute::NonNull);
-            Changed = true;
+            CHANGED = true;
           }
         }
       }
     }
     if (!isGuaranteedToTransferExecutionToSuccessor(&I))
       break;
   }
 
-  return Changed;
+  return CHANGED;
 }
 
 /// Deduce nocapture attributes for the SCC.
 static bool addArgumentAttrs(const SCCNodeSet &SCCNodes) {
-  bool Changed = false;
+  bool CHANGED = false;
+  bool NEWCAPTURE = false;
 
   ArgumentGraph AG;
 
   // Check each function in turn, determining which pointer arguments are not
   // captured.
   for (Function *F : SCCNodes) {
     // We can infer and propagate function attributes only when we know that the
     // definition we'll get at link time is *exactly* the definition we see now.
-    // For more details, see GlobalValue::mayBeDerefined.
+    // For more details, see GlobalValue::canBeDerefined.
     if (!F->hasExactDefinition())
       continue;
 
-    Changed |= addArgumentAttrsFromCallsites(*F);
+    CHANGED |= addArgumentAttrsFromCallsites(*F);
 
     // Functions that are readonly (or readnone) and nounwind and don't return
     // 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) {
         if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) {
           A->addAttr(Attribute::NoCapture);
           ++NumNoCapture;
-          Changed = true;
+          CHANGED = true;
+          NEWCAPTURE = true;
+          F->dump();
         }
       }
       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);
         PointerMayBeCaptured(&*A, &Tracker);
         if (!Tracker.Captured) {
           if (Tracker.Uses.empty()) {
             // If it's trivially not captured, mark it nocapture now.
             A->addAttr(Attribute::NoCapture);
             ++NumNoCapture;
-            Changed = true;
+            CHANGED = true;
+            NEWCAPTURE = true;
+            F->dump();
           } else {
             // If it's not trivially captured and not trivially not captured,
             // then it must be calling into another function in our SCC. Save
             // its particulars for Argument-SCC analysis later.
             ArgumentGraphNode *Node = AG[&*A];
             for (Argument *Use : Tracker.Uses) {
               Node->Uses.push_back(AG[Use]);
               if (Use != &*A)
                 HasNonLocalUses = true;
             }
           }
         }
         // Otherwise, it's captured. Don't bother doing SCC analysis on it.
       }
       if (!HasNonLocalUses && !A->onlyReadsMemory()) {
         // Can we determine that it's readonly/readnone without doing an 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;
         Self.insert(&*A);
         Attribute::AttrKind R = determinePointerReadAttrs(&*A, Self);
         if (R != Attribute::None) {
           A->addAttr(R);
-          Changed = true;
+          CHANGED = true;
           R == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
+          A->getParent()->dump();
         }
       }
     }
   }
 
   // The graph we've collected is partial because we stopped scanning for
   // argument uses once we solved the argument trivially. These partial nodes
   // show up as ArgumentGraphNode objects with an empty Uses list, and for
   // these nodes the final decision about whether they capture has already been
   // 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) {
     const std::vector<ArgumentGraphNode *> &ArgumentSCC = *I;
     if (ArgumentSCC.size() == 1) {
       if (!ArgumentSCC[0]->Definition)
         continue; // synthetic root node
 
       // eg. "void f(int* x) { if (...) f(x); }"
       if (ArgumentSCC[0]->Uses.size() == 1 &&
           ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) {
         Argument *A = ArgumentSCC[0]->Definition;
         A->addAttr(Attribute::NoCapture);
         ++NumNoCapture;
-        Changed = true;
+        CHANGED = true;
+        NEWCAPTURE = true;
+        ArgumentSCC[0]->Definition->getParent()->dump();
       }
       continue;
     }
 
     bool SCCCaptured = false;
     for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
          I != E && !SCCCaptured; ++I) {
       ArgumentGraphNode *Node = *I;
for (scc_iterator<ArgumentGraph *> I = scc_begin(&AG); !I.isAtEnd(); ++I) {
     }
     if (SCCCaptured)
       continue;
 
     for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
       Argument *A = ArgumentSCC[i]->Definition;
       A->addAttr(Attribute::NoCapture);
       ++NumNoCapture;
-      Changed = true;
+      CHANGED = true;
+      NEWCAPTURE = true;
+      A->getParent()->dump();
     }
 
     // We also want to compute readonly/readnone. With a small number of false
     // negatives, we can assume that any pointer which is captured isn't going
     // to be provably readonly or readnone, since by definition we can't
     // analyze all uses of a captured pointer.
     //
     // The false negatives happen when the pointer is captured by a function
for (scc_iterator<ArgumentGraph *> I = scc_begin(&AG); !I.isAtEnd(); ++I) {
     if (ReadAttr != Attribute::None) {
       for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
         Argument *A = ArgumentSCC[i]->Definition;
         // Clear out existing readonly/readnone attributes
         A->removeAttr(Attribute::ReadOnly);
         A->removeAttr(Attribute::ReadNone);
         A->addAttr(ReadAttr);
         ReadAttr == Attribute::ReadOnly ? ++NumReadOnlyArg : ++NumReadNoneArg;
-        Changed = true;
+        CHANGED = true;
+        A->getParent()->dump();
       }
     }
   }
 
-  return Changed;
+  assert(!NEWCAPTURE);
+  assert(!CHANGED);
+  return CHANGED;
 }
 
 /// 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.
 static bool isFunctionMallocLike(Function *F, const SCCNodeSet &SCCNodes) {
   SmallSetVector<Value *, 8> FlowsToReturn;
if (!F->getReturnType()->isPointerTy())
       continue;
 
     if (!isFunctionMallocLike(F, SCCNodes))
       return false;
   }
 
   bool MadeChange = false;
   for (Function *F : SCCNodes) {
-    if (F->returnDoesNotAlias() ||
-        !F->getReturnType()->isPointerTy())
+    if (F->returnDoesNotAlias() || !F->getReturnType()->isPointerTy())
       continue;
 
     F->setReturnDoesNotAlias();
     ++NumNoAlias;
     MadeChange = true;
   }
 
+  // if (MadeChange)
+  //(*SCCNodes.begin())->getParent()->dump();
+  // assert(!MadeChange);
   return MadeChange;
 }
 
 /// Tests whether this function is known to not return null.
 ///
 /// Requires that the function returns a pointer.
 ///
 /// Returns true if it believes the function will not return a null, and sets
for (Function *F : SCCNodes) {
     if (!F->getReturnType()->isPointerTy())
       continue;
 
     bool Speculative = false;
     if (isReturnNonNull(F, SCCNodes, Speculative)) {
       if (!Speculative) {
         // Mark the function eagerly since we may discover a function
         // which prevents us from speculating about the entire SCC
-        LLVM_DEBUG(dbgs() << "Eagerly marking " << F->getName()
-                          << " as nonnull\n");
+        (dbgs() << "Eagerly marking " << F->getName() << " as nonnull\n");
         F->addAttribute(AttributeList::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 (Function *F : SCCNodes) {
       if (F->getAttributes().hasAttribute(AttributeList::ReturnIndex,
                                           Attribute::NonNull) ||
           !F->getReturnType()->isPointerTy())
         continue;
 
-      LLVM_DEBUG(dbgs() << "SCC marking " << F->getName() << " as nonnull\n");
+      (dbgs() << "SCC marking " << F->getName() << " as nonnull\n");
       F->addAttribute(AttributeList::ReturnIndex, Attribute::NonNull);
       ++NumNonNullReturn;
       MadeChange = true;
     }
   }
 
+  if (MadeChange)
+    (*SCCNodes.begin())->getParent()->dump();
+  assert(!MadeChange);
   return MadeChange;
 }
 
 namespace {
 
 /// Collects a set of attribute inference requests and performs them all in one
 /// go on a single SCC Node. Inference involves scanning function bodies
 /// looking for instructions that violate attribute assumptions.
llvm::erase_if(InferInSCC, [F](const InferenceDescriptor &ID) {
 
       // Remove from further inference (invalidate) when visiting a function
       // that has no instructions to scan/has an unsuitable definition.
       return F->isDeclaration() ||
              (ID.RequiresExactDefinition && !F->hasExactDefinition());
     });
 
     // For each attribute still in InferInSCC that doesn't explicitly skip F,
-    // set up the F instructions scan to verify assumptions of the attribute.
+    // set up the F instructions scan to isConsistent assumptions of the
+    // attribute.
     SmallVector<InferenceDescriptor, 4> InferInThisFunc;
     llvm::copy_if(
         InferInSCC, std::back_inserter(InferInThisFunc),
         [F](const InferenceDescriptor &ID) { return !ID.SkipFunction(*F); });
 
     if (InferInThisFunc.empty())
       continue;
 
for (Instruction &I : instructions(*F)) {
       if (InferInThisFunc.empty())
         break;
     }
   }
 
   if (InferInSCC.empty())
     return false;
 
-  bool Changed = false;
+  bool CHANGED = false;
   for (Function *F : SCCNodes)
     // At this point InferInSCC contains only functions that were either:
     //   - explicitly skipped from scan/inference, or
     //   - verified to have no instructions that break attribute assumptions.
     // Hence we just go and force the attribute for all non-skipped functions.
     for (auto &ID : InferInSCC) {
       if (ID.SkipFunction(*F))
         continue;
-      Changed = true;
+      CHANGED = true;
       ID.SetAttribute(*F);
     }
-  return Changed;
+  return CHANGED;
 }
 
 } // end anonymous namespace
 
 /// Helper for non-Convergent inference predicate InstrBreaksAttribute.
 static bool InstrBreaksNonConvergent(Instruction &I,
                                      const SCCNodeSet &SCCNodes) {
   const CallSite CS(&I);
static bool addNoRecurseAttrs(const SCCNodeSet &SCCNodes) {
   // Every call was to a non-recursive function other than this function, and
   // we have no indirect recursion as the SCC size is one. This function cannot
   // recurse.
   return setDoesNotRecurse(*F);
 }
 
 template <typename AARGetterT>
 static bool deriveAttrsInPostOrder(SCCNodeSet &SCCNodes, AARGetterT &&AARGetter,
-                                   bool HasUnknownCall) {
-  bool Changed = false;
+                                   DTGetterTy &DTGetter, bool HasUnknownCall) {
+  bool CHANGED = false;
 
   // Bail if the SCC only contains optnone functions.
   if (SCCNodes.empty())
-    return Changed;
+    return CHANGED;
 
-  Changed |= addArgumentReturnedAttrs(SCCNodes);
-  Changed |= addReadAttrs(SCCNodes, AARGetter);
-  Changed |= addArgumentAttrs(SCCNodes);
+  CHANGED |= addArgumentReturnedAttrs(SCCNodes);
+  CHANGED |= addReadAttrs(SCCNodes, AARGetter);
+  CHANGED |= addArgumentAttrs(SCCNodes);
 
   // If we have no external nodes participating in the SCC, we can deduce some
   // more precise attributes as well.
   if (!HasUnknownCall) {
-    Changed |= addNoAliasAttrs(SCCNodes);
-    Changed |= addNonNullAttrs(SCCNodes);
-    Changed |= inferAttrsFromFunctionBodies(SCCNodes);
-    Changed |= addNoRecurseAttrs(SCCNodes);
+    CHANGED |= addNoAliasAttrs(SCCNodes);
+    CHANGED |= addNonNullAttrs(SCCNodes);
+    CHANGED |= inferAttrsFromFunctionBodies(SCCNodes);
+    CHANGED |= addNoRecurseAttrs(SCCNodes);
   }
 
-  return Changed;
+  return CHANGED;
 }
 
 PreservedAnalyses PostOrderFunctionAttrsPass::run(LazyCallGraph::SCC &C,
                                                   CGSCCAnalysisManager &AM,
                                                   LazyCallGraph &CG,
                                                   CGSCCUpdateResult &) {
   FunctionAnalysisManager &FAM =
       AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
 
   // We pass a lambda into functions to wire them up to the analysis manager
   // for getting function analyses.
-  auto AARGetter = [&](Function &F) -> AAResults & {
-    return FAM.getResult<AAManager>(F);
+  std::function<AAResults &(Function &)> AARGetter =
+      [&](Function &F) -> AAResults & { return FAM.getResult<AAManager>(F); };
+  DTGetterTy DTGetter = [&](Function &F) -> const DominatorTree & {
+    return FAM.getResult<DominatorTreeAnalysis>(F);
   };
 
   // Fill SCCNodes with the elements of the SCC. Also track whether there are
   // any external or opt-none nodes that will prevent us from optimizing any
   // part of the SCC.
   SCCNodeSet SCCNodes;
   bool HasUnknownCall = false;
   for (LazyCallGraph::Node &N : C) {
if (!HasUnknownCall)
           if (!CS.getCalledFunction()) {
             HasUnknownCall = true;
             break;
           }
 
     SCCNodes.insert(&F);
   }
 
-  if (deriveAttrsInPostOrder(SCCNodes, AARGetter, HasUnknownCall))
+  if (SCCNodes.size()) {
+    Attributor A(AARGetter, DTGetter);
+    A.run(*SCCNodes.front()->getParent());
+  }
+
+  if (deriveAttrsInPostOrder(SCCNodes, AARGetter, DTGetter, HasUnknownCall))
     return PreservedAnalyses::none();
 
   return PreservedAnalyses::all();
 }
 
 namespace {
 
-struct PostOrderFunctionAttrsLegacyPass : public CallGraphSCCPass {
+struct PostOrderFunctionAttrsLegacyPass : public ModulePass {
+  // struct PostOrderFunctionAttrsLegacyPass : public CallGraphSCCPass {
   // Pass identification, replacement for typeid
   static char ID;
 
-  PostOrderFunctionAttrsLegacyPass() : CallGraphSCCPass(ID) {
+  // PostOrderFunctionAttrsLegacyPass() : CallGraphSCCPass(ID) {
+  PostOrderFunctionAttrsLegacyPass() : ModulePass(ID) {
     initializePostOrderFunctionAttrsLegacyPassPass(
         *PassRegistry::getPassRegistry());
   }
 
-  bool runOnSCC(CallGraphSCC &SCC) override;
+  bool runOnModule(Module &M) override;
+  // bool runOnSCC(CallGraphSCC &SCC) override;
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     AU.addRequired<AssumptionCacheTracker>();
     getAAResultsAnalysisUsage(AU);
-    CallGraphSCCPass::getAnalysisUsage(AU);
+    AU.addRequired<DominatorTreeWrapperPass>();
+    AU.addRequired<CallGraphWrapperPass>();
+
+    AU.addPreserved<DominatorTreeWrapperPass>();
+    AU.addPreserved<AssumptionCacheTracker>();
+    AU.addPreserved<CallGraphWrapperPass>();
+    AU.addPreserved<GlobalsAAWrapperPass>();
+    // CallGraphSCCPass::getAnalysisUsage(AU);
   }
 };
 
 } // end anonymous namespace
 
 char PostOrderFunctionAttrsLegacyPass::ID = 0;
 INITIALIZE_PASS_BEGIN(PostOrderFunctionAttrsLegacyPass, "functionattrs",
                       "Deduce function attributes", false, false)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_END(PostOrderFunctionAttrsLegacyPass, "functionattrs",
                     "Deduce function attributes", false, false)
 
 Pass *llvm::createPostOrderFunctionAttrsLegacyPass() {
   return new PostOrderFunctionAttrsLegacyPass();
 }
 
-template <typename AARGetterT>
-static bool runImpl(CallGraphSCC &SCC, AARGetterT AARGetter) {
+template <typename CGSCC, typename AARGetterT>
+static bool runImpl(CGSCC &SCC, AARGetterT AARGetter, DTGetterTy &DTGetter,
+                    Attributor &A) {
 
   // Fill SCCNodes with the elements of the SCC. Used for quickly looking up
   // whether a given CallGraphNode is in this SCC. Also track whether there are
   // any external or opt-none nodes that will prevent us from optimizing any
   // part of the SCC.
   SCCNodeSet SCCNodes;
   bool ExternalNode = false;
-  for (CallGraphNode *I : SCC) {
+  for (auto *I : SCC) {
     Function *F = I->getFunction();
     if (!F || F->hasFnAttribute(Attribute::OptimizeNone) ||
         F->hasFnAttribute(Attribute::Naked)) {
       // External node or function we're trying not to optimize - we both avoid
       // transform them and avoid leveraging information they provide.
       ExternalNode = true;
       continue;
     }
 
     SCCNodes.insert(F);
   }
 
-  return deriveAttrsInPostOrder(SCCNodes, AARGetter, ExternalNode);
+  return deriveAttrsInPostOrder(SCCNodes, AARGetter, DTGetter, ExternalNode);
+}
+
+bool PostOrderFunctionAttrsLegacyPass::runOnModule(Module &M) {
+  if (skipModule(M))
+    return false;
+
+  LegacyAARGetter LAARGetter(*this);
+  std::function<AAResults &(Function &)> AARGetter =
+      [&](Function &F) -> AAResults & { return LAARGetter(F); };
+  DTGetterTy DTGetter = [&](Function &F) -> const DominatorTree & {
+    return getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
+  };
+
+  Attributor A(AARGetter, DTGetter);
+  A.run(M);
+
+  bool Changed = false;
+  auto &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
+  for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I)
+    Changed |= runImpl(*I, AARGetter, DTGetter, A);
+
+  return Changed;
 }
 
+#if 0
 bool PostOrderFunctionAttrsLegacyPass::runOnSCC(CallGraphSCC &SCC) {
   if (skipSCC(SCC))
     return false;
-  return runImpl(SCC, LegacyAARGetter(*this));
+
+  LegacyAARGetter LAARGetter(*this);
+  std::function<AAResults &(Function &)> AARGetter =
+      [&](Function &F) -> AAResults & { return LAARGetter(F); };
+  DenseMap<Function *, const DominatorTree *> DTMap;
+  DTGetterTy DTGetter = [&](Function &F) -> const DominatorTree & {
+    auto *&DT = DTMap[&F];
+    if (!DT) {
+      DT = new DominatorTree(F);
     }
+    return *DT;
+  };
+
+  return runImpl(SCC, AARGetter, DTGetter, A);
+}
+#endif
 
 namespace {
 
 struct ReversePostOrderFunctionAttrsLegacyPass : public ModulePass {
   // Pass identification, replacement for typeid
   static char ID;
 
   ReversePostOrderFunctionAttrsLegacyPass() : ModulePass(ID) {
void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addPreserved<CallGraphWrapperPass>();
   }
 };
 
 } // end anonymous namespace
 
 char ReversePostOrderFunctionAttrsLegacyPass::ID = 0;
 
-INITIALIZE_PASS_BEGIN(ReversePostOrderFunctionAttrsLegacyPass, "rpo-functionattrs",
-                      "Deduce function attributes in RPO", false, false)
+INITIALIZE_PASS_BEGIN(ReversePostOrderFunctionAttrsLegacyPass,
+                      "rpo-functionattrs", "Deduce function attributes in RPO",
+                      false, false)
 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
-INITIALIZE_PASS_END(ReversePostOrderFunctionAttrsLegacyPass, "rpo-functionattrs",
-                    "Deduce function attributes in RPO", false, false)
+INITIALIZE_PASS_END(ReversePostOrderFunctionAttrsLegacyPass,
+                    "rpo-functionattrs", "Deduce function attributes in RPO",
+                    false, false)
 
 Pass *llvm::createReversePostOrderFunctionAttrsPass() {
   return new ReversePostOrderFunctionAttrsLegacyPass();
 }
 
 static bool addNoRecurseAttrsTopDown(Function &F) {
   // We check the preconditions for the function prior to calling this to avoid
   // the cost of building up a reversible post-order list. We assert them here
for (auto *U : F.users()) {
     if (!CS || !CS.getParent()->getParent()->doesNotRecurse())
       return false;
   }
   return setDoesNotRecurse(F);
 }
 
 static bool deduceFunctionAttributeInRPO(Module &M, CallGraph &CG) {
   // We only have a post-order SCC traversal (because SCCs are inherently
-  // discovered in post-order), so we accumulate them in a vector and then walk
-  // it in reverse. This is simpler than using the RPO iterator infrastructure
   // because we need to combine SCC detection and the PO walk of the call
   // graph. We can also cheat egregiously because we're primarily interested in
   // synthesizing norecurse and so we can only save the singular SCCs as SCCs
   // with multiple functions in them will clearly be recursive.
   SmallVector<Function *, 16> Worklist;
   for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
     if (I->size() != 1)
       continue;
 
     Function *F = I->front()->getFunction();
     if (F && !F->isDeclaration() && !F->doesNotRecurse() &&
         F->hasInternalLinkage())
       Worklist.push_back(F);
   }
 
-  bool Changed = false;
+  bool Changed = UNCHANGED;
   for (auto *F : llvm::reverse(Worklist))
     Changed |= addNoRecurseAttrsTopDown(*F);
 
   return Changed;
 }
 
 bool ReversePostOrderFunctionAttrsLegacyPass::runOnModule(Module &M) {
   if (skipModule(M))
ReversePostOrderFunctionAttrsPass::run(Module &M, ModuleAnalysisManager &AM) {
 
   if (!deduceFunctionAttributeInRPO(M, CG))
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
   PA.preserve<CallGraphAnalysis>();
   return PA;
 }
+//===- FunctionAttrs.cpp - Pass which marks functions attributes ----------===//
+//

lib/Transforms/IPO/PassManagerBuilder.cpp

void PassManagerBuilder::populateModulePassManager(
   // not run it a second time
   if (!PerformThinLTO && !PrepareForThinLTOUsingPGOSampleProfile)
     addPGOInstrPasses(MPM);
 
   // We add a module alias analysis pass here. In part due to bugs in the
   // analysis infrastructure this "works" in that the analysis stays alive
   // for the entire SCC pass run below.
   MPM.add(createGlobalsAAWrapperPass());
+  MPM.add(createPostOrderFunctionAttrsLegacyPass());
 
   // Start of CallGraph SCC passes.
   MPM.add(createPruneEHPass()); // Remove dead EH info
   bool RunInliner = false;
   if (Inliner) {
     MPM.add(Inliner);
     Inliner = nullptr;
     RunInliner = true;
   }
 
-  MPM.add(createPostOrderFunctionAttrsLegacyPass());
   if (OptLevel > 2)
     MPM.add(createArgumentPromotionPass()); // Scalarize uninlined fn args
 
   addExtensionsToPM(EP_CGSCCOptimizerLate, MPM);
   addFunctionSimplificationPasses(MPM);
 
   // FIXME: This is a HACK! The inliner pass above implicitly creates a CGSCC
   // pass manager that we are specifically trying to avoid. To prevent this
if (OptLevel > 1 && !PrepareForLTO && !PrepareForThinLTO)
     // are unreferenced they will be removed by GlobalDCE later, so
     // this only impacts referenced available externally globals.
     // Eventually they will be suppressed during codegen, but eliminating
     // here enables more opportunity for GlobalDCE as it may make
     // globals referenced by available external functions dead
     // and saves running remaining passes on the eliminated functions.
     MPM.add(createEliminateAvailableExternallyPass());
 
+  MPM.add(createPostOrderFunctionAttrsLegacyPass());
   MPM.add(createReversePostOrderFunctionAttrsPass());
 
   // The inliner performs some kind of dead code elimination as it goes,
   // but there are cases that are not really caught by it. We might
   // at some point consider teaching the inliner about them, but it
   // is OK for now to run GlobalOpt + GlobalDCE in tandem as their
   // benefits generally outweight the cost, making the whole pipeline
   // faster.
void PassManagerBuilder::addLTOOptimizationPasses(legacy::PassManagerBase &PM) {
   // Provide AliasAnalysis services for optimizations.
   addInitialAliasAnalysisPasses(PM);
 
   // Allow forcing function attributes as a debugging and tuning aid.
   PM.add(createForceFunctionAttrsLegacyPass());
 
   // Infer attributes about declarations if possible.
   PM.add(createInferFunctionAttrsLegacyPass());
+  PM.add(createPostOrderFunctionAttrsLegacyPass());
 
   if (OptLevel > 1) {
     // Split call-site with more constrained arguments.
     PM.add(createCallSiteSplittingPass());
 
     // Indirect call promotion. This should promote all the targets that are
     // left by the earlier promotion pass that promotes intra-module targets.
     // This two-step promotion is to save the compile time. For LTO, it should
     // produce the same result as if we only do promotion here.
     PM.add(
         createPGOIndirectCallPromotionLegacyPass(true, !PGOSampleUse.empty()));
 
     // Propagate constants at call sites into the functions they call.  This
     // opens opportunities for globalopt (and inlining) by substituting function
     // pointers passed as arguments to direct uses of functions.
     PM.add(createIPSCCPPass());
 
     // Attach metadata to indirect call sites indicating the set of functions
     // they may target at run-time. This should follow IPSCCP.
     PM.add(createCalledValuePropagationPass());
   }
 
   // Infer attributes about definitions. The readnone attribute in particular is
   // required for virtual constant propagation.
-  PM.add(createPostOrderFunctionAttrsLegacyPass());
   PM.add(createReversePostOrderFunctionAttrsPass());
 
   // Split globals using inrange annotations on GEP indices. This can help
   // improve the quality of generated code when virtual constant propagation or
   // control flow integrity are enabled.
   PM.add(createGlobalSplitPass());
 
   // Apply whole-program devirtualization and virtual constant propagation.
void PassManagerBuilder::addLTOOptimizationPasses(legacy::PassManagerBase &PM) {
   addInstructionCombiningPass(PM);
   addExtensionsToPM(EP_Peephole, PM);
   PM.add(createJumpThreadingPass());
 
   // Break up allocas
   PM.add(createSROAPass());
 
   // Run a few AA driven optimizations here and now, to cleanup the code.
-  PM.add(createPostOrderFunctionAttrsLegacyPass()); // Add nocapture.
   PM.add(createGlobalsAAWrapperPass()); // IP alias analysis.
+  PM.add(createPostOrderFunctionAttrsLegacyPass()); // Add nocapture.
 
   PM.add(createLICMPass());                 // Hoist loop invariants.
   PM.add(createMergedLoadStoreMotionPass()); // Merge ld/st in diamonds.
   PM.add(NewGVN ? createNewGVNPass()
                 : createGVNPass(DisableGVNLoadPRE)); // Remove redundancies.
   PM.add(createMemCpyOptPass());            // Remove dead memcpys.
 
   // Nuke dead stores.

test/Analysis/TypeBasedAliasAnalysis/functionattrs.ll

 ; RUN: opt < %s -tbaa -basicaa -functionattrs -S | FileCheck %s
 
 ; FunctionAttrs should make use of TBAA.
 
 ; Add the readnone attribute, since the only access is a store which TBAA
 ; says is to constant memory.
 ;
 ; It's unusual to see a store to constant memory, but it isn't necessarily
 ; invalid, as it's possible that this only happens after optimization on a
 ; code path which isn't ever executed.
 
-; CHECK: define void @test0_yes(i32* nocapture %p) #0 {
+; CHECK: define void @test0_yes(i32* nocapture nonnull dereferenceable(4) %p) #0 {
 define void @test0_yes(i32* %p) nounwind {
   store i32 0, i32* %p, !tbaa !1
   ret void
 }
 
-; CHECK: define void @test0_no(i32* nocapture %p) #1 {
+; CHECK: define void @test0_no(i32* nocapture nonnull dereferenceable(4) %p) #1 {
 define void @test0_no(i32* %p) nounwind {
   store i32 0, i32* %p, !tbaa !2
   ret void
 }
 
 ; Add the readonly attribute, since there's just a call to a function which 
 ; TBAA says doesn't modify any memory.
 

test/ThinLTO/X86/devirt-after-icp.ll

if.true.direct_targ:                              ; preds = %entry
   %6 = bitcast i32 (%class.A*)** %vtable to i8*
   %7 = tail call i1 @llvm.type.test(i8* %6, metadata !"_ZTS1B")
   tail call void @llvm.assume(i1 %7)
   %vfn.i1 = getelementptr inbounds i32 (%class.A*)*, i32 (%class.A*)** %vtable, i64 1
   %vfn.i = bitcast i32 (%class.A*)** %vfn.i1 to i32 (%class.B*)**
   %8 = load i32 (%class.B*)*, i32 (%class.B*)** %vfn.i, align 8
 ; Call to bar() can be devirtualized to call to B::bar(), since it was
 ; inlined from B::foo() after ICP introduced the guarded promotion.
-; CHECK-IR: %call.i = tail call i32 @_ZN1B3barEv(%class.B* %3)
+; CHECK-IR: %call.i = tail call i32 @_ZN1B3barEv(%class.B* nonnull %3)
   %call.i = tail call i32 %8(%class.B* %5)
   br label %if.end.icp
 
 ; This block contains the fallback indirect call a->foo()
 ; CHECK-IR: if.false.orig_indirect:
 if.false.orig_indirect:                           ; preds = %entry
 ; Fallback indirect call to foo() cannot be devirtualized.
 ; CHECK-IR: %call = tail call i32 %

test/Transforms/FunctionAttrs/2009-01-02-LocalStores.ll

 ; RUN: opt < %s -functionattrs -S | FileCheck %s
 ; RUN: opt < %s -passes=function-attrs -S | FileCheck %s
 
-; CHECK: define i32* @a(i32** nocapture readonly %p)
+; CHECK: define i32* @a(i32** nocapture nonnull readonly dereferenceable(8) %p)
 define i32* @a(i32** %p) {
   %tmp = load i32*, i32** %p
   ret i32* %tmp
 }
 
 ; CHECK: define i32* @b(i32* %q)
 define i32* @b(i32 *%q) {
   %mem = alloca i32*
   store i32* %q, i32** %mem
   %tmp = call i32* @a(i32** %mem)
   ret i32* %tmp
 }
-
-; CHECK: define i32* @c(i32* readnone returned %r)
-@g = global i32 0
-define i32* @c(i32 *%r) {
-  %a = icmp eq i32* %r, null
-  store i32 1, i32* @g
-  ret i32* %r
-}

test/Transforms/FunctionAttrs/atomic.ll

 ; RUN: opt -basicaa -functionattrs -S < %s | FileCheck %s
 ; RUN: opt -aa-pipeline=basic-aa -passes=function-attrs -S < %s | FileCheck %s
 
 ; Atomic load/store to local doesn't affect whether a function is
 ; readnone/readonly.
 define i32 @test1(i32 %x) uwtable ssp {
 ; CHECK: define i32 @test1(i32 %x) #0 {
 entry:
   %x.addr = alloca i32, align 4
   store atomic i32 %x, i32* %x.addr seq_cst, align 4
   %r = load atomic i32, i32* %x.addr seq_cst, align 4
   ret i32 %r
 }
 
 ; A function with an Acquire load is not readonly.
 define i32 @test2(i32* %x) uwtable ssp {
-; CHECK: define i32 @test2(i32* nocapture readonly %x) #1 {
+; CHECK: define i32 @test2(i32* nocapture nonnull readonly dereferenceable(4) %x) #1 {
 entry:
   %r = load atomic i32, i32* %x seq_cst, align 4
   ret i32 %r
 }
 
 ; CHECK: attributes #0 = { norecurse nounwind readnone ssp uwtable }
-; CHECK: attributes #1 = { norecurse nounwind ssp uwtable }
+; CHECK: attributes #1 = { argmemonly norecurse nounwind ssp uwtable }

test/Transforms/FunctionAttrs/attribute_propagation.ll

+; RUN: opt -functionattrs -S < %s | FileCheck %s
+;
+;    void foo(int *A) {
+;      bar(A);
+;    }
+;
+;    void bar(int *A) {
+;      baz(A - 33);
+;    }
+;
+;    void baz(int *A) {
+;      A[100] = 0;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; CHECK: define dso_local void @foo(i32* nocapture nonnull dereferenceable(536) %A)
+define dso_local void @foo(i32* %A) {
+entry:
+  call void @bar(i32* %A)
+  ret void
+}
+
+; CHECK: define dso_local void @bar(i32* nocapture nonnull dereferenceable(536) %B)
+define dso_local void @bar(i32* %B) {
+entry:
+  %add.ptr = getelementptr inbounds i32, i32* %B, i64 -33
+  call void @baz(i32* %add.ptr)
+  ret void
+}
+
+define dso_local void @baz(i32* %C) {
+entry:
+  %arrayidx = getelementptr inbounds i32, i32* %C, i64 100
+  store i32 0, i32* %arrayidx, align 4
+  ret void
+}
+

test/Transforms/FunctionAttrs/attribute_propagation_chain.ll

+; RUN: opt -functionattrs -S < %s | FileCheck %s
+;
+;    void a(int *A) {
+;      A[-4] = 0;
+;    }
+;    void b(int *A) {
+;      A[100] = 0;
+;      a(A);
+;    }
+;    void c(int *A) {
+;      b(A);
+;    }
+;    void d(int *A) {
+;      c(A + 1);
+;    }
+;    void e(int *A) {
+;      d(A - 1);
+;    }
+;    void f(int *A) {
+;      e(A);
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define dso_local void @a0(i64* %A) {
+entry:
+  %arrayidx = getelementptr inbounds i64, i64* %A, i64 -3
+  %bc8 = bitcast i64* %arrayidx to i8*
+  store i8 0, i8* %bc8, align 4
+  ret void
+}
+
+define dso_local void @a1(i64* %A) {
+entry:
+  %arrayidx = getelementptr inbounds i64, i64* %A, i64 -3
+  %bc32 = bitcast i64* %arrayidx to <8 x i32>*
+  store <8 x i32> undef, <8 x i32>* %bc32, align 16
+  ret void
+}
+
+define dso_local void @a2(i64* %A) {
+entry:
+  %arrayidx = getelementptr inbounds i64, i64* %A, i64 -3
+  %bc64 = bitcast i64* %arrayidx to <8 x i64>*
+  store <8 x i64> undef, <8 x i64>* %bc64, align 16
+  ret void
+}
+
+define dso_local void @b(i64* %A) {
+entry:
+  %arrayidx = getelementptr inbounds i64, i64* %A, i64 100
+  store i64 0, i64* %arrayidx, align 4
+  call void @a0(i64* %A)
+  call void @a1(i64* %A)
+  call void @a2(i64* %A)
+  ret void
+}
+
+define dso_local void @c(i64* %A) {
+entry:
+  call void @b(i64* %A)
+  ret void
+}
+
+define dso_local void @d(i64* %A) {
+entry:
+  %add.ptr = getelementptr inbounds i64, i64* %A, i64 1
+  call void @c(i64* nonnull %add.ptr)
+  ret void
+}
+
+define dso_local void @e(i64* %A) {
+entry:
+  %add.ptr = getelementptr inbounds i64, i64* %A, i64 -1
+  call void @d(i64* nonnull %add.ptr)
+  ret void
+}
+
+define dso_local void @f(i64* %A) {
+entry:
+  call void @e(i64* %A)
+  ret void
+}

test/Transforms/FunctionAttrs/internal_callee.ll

+; RUN: opt -S -functionattrs < %s | FileCheck %s
+;
+; Check that we derive the noalias and dereferenceable_or_null attribute
+; for the argument of the rec_internal function.
+;
+; If nonnull propagation is enabled we should combine dereferenceable_or_null
+; and nonnull to dereferenceable.
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; Function Attrs: noinline nounwind uwtable
+define dso_local void @g(i32* noalias dereferenceable_or_null(4) %A) #0 {
+entry:
+  call void @rec_internal(i32* nonnull %A)
+  ret void
+}
+
+; Function Attrs: noinline nounwind uwtable
+define dso_local void @h() #0 {
+entry:
+  %A = alloca i32, align 4
+  store i32 5, i32* %A, align 4
+  call void @rec_internal(i32* nonnull %A)
+  ret void
+}
+
+; CHECK: define internal void @rec_internal(i32* noalias nocapture nonnull dereferenceable(4) %A)
+;
+; Function Attrs: noinline nounwind uwtable
+define internal void @rec_internal(i32* %A) #1 {
+entry:
+  %0 = load i32, i32* %A, align 4
+  %sub = add nsw i32 %0, -1
+  store i32 %sub, i32* %A, align 4
+  %tobool = icmp eq i32 %sub, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  call void @rec_internal(i32* %A)
+  br label %if.end
+
+if.end:                                           ; preds = %entry, %if.then
+  ret void
+}
+
+; CHECK: define void @rec(i32* nocapture nonnull dereferenceable(4) %A)
+define void @rec(i32* %A) #0 {
+entry:
+  %0 = load i32, i32* %A, align 4
+  %sub = add nsw i32 %0, -1
+  store i32 %sub, i32* %A, align 4
+  %tobool = icmp eq i32 %sub, 0
+  br i1 %tobool, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  call void @rec(i32* %A)
+  br label %if.end
+
+if.end:                                           ; preds = %entry, %if.then
+  ret void
+}
+
+attributes #0 = { noinline nounwind uwtable }
+attributes #1 = { argmemonly noinline nounwind uwtable }

test/Transforms/FunctionAttrs/internal_large-agg.ll

+; RUN: opt -S -functionattrs < %s | FileCheck %s
+; RUN: opt -S -functionattrs -rpo-functionattrs -enable-nonnull-arg-prop < %s | FileCheck %s
+;
+; This test was taken from D4609, slightly simplified, and ported to
+; the new encoding.
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+%struct.s = type { [65280 x i32] }
+%struct.x = type opaque
+%struct.x.0 = type opaque
+
+; CHECK: define void @bar()
+
+define void @bar() {
+entry:
+  %x = alloca %struct.s, align 32
+  %y = alloca %struct.s, align 4
+  %0 = bitcast %struct.s* %x to i8*
+  call void @llvm.lifetime.start(i64 261120, i8* %0)
+  %1 = bitcast %struct.s* %y to i8*
+  call void @llvm.lifetime.start(i64 261120, i8* %1)
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds %struct.s, %struct.s* %x, i64 0, i32 0, i64 %indvars.iv
+  %2 = trunc i64 %indvars.iv to i32
+  store i32 %2, i32* %arrayidx, align 4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 17800
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  %3 = bitcast %struct.s* %y to %struct.x*
+  call fastcc void @foo(%struct.s* %x, %struct.x* %3)
+  call void @llvm.lifetime.end(i64 261120, i8* %1)
+  call void @llvm.lifetime.end(i64 261120, i8* %0)
+  ret void
+}
+
+declare void @llvm.lifetime.start(i64, i8* nocapture)
+
+; CHECK: define internal fastcc void @foo(%struct.s* noalias nocapture nonnull readonly dereferenceable(261120) %x, %struct.x* noalias nonnull dereferenceable(261120) %y)
+
+define internal fastcc void @foo(%struct.s* %x, %struct.x* %y) {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %sum.05 = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %arrayidx = getelementptr inbounds %struct.s, %struct.s* %x, i64 0, i32 0, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %add = add nsw i32 %0, %sum.05
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 16000
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  %1 = bitcast %struct.x* %y to %struct.x.0*
+  tail call void @goo(i32 %add, %struct.x.0* %1)
+  ret void
+}
+
+declare void @llvm.lifetime.end(i64, i8* nocapture)
+
+declare void @goo(i32, %struct.x.0*)

test/Transforms/FunctionAttrs/internal_malloc.ll

+; RUN: opt -S -functionattrs < %s | FileCheck %s
+;
+; This test was taken from D4609, slightly simplified, and ported to
+; the new encoding.
+;
+; TODO: It seems no pass determines the initial dereferenceable_or_null
+;       attribute for the malloc so we have to place it ourselves.
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define i32 @bar() {
+entry:
+  %call = tail call noalias dereferenceable_or_null(12345) i8* @malloc(i64 12345)
+  %0 = bitcast i8* %call to i32*
+  store i32 10, i32* %0, align 4
+  tail call fastcc void @foo(i32* %0)
+  ret i32 0
+}
+
+declare noalias i8* @malloc(i64)
+
+
+; CHECK: define internal fastcc void @foo(i32* noalias nonnull dereferenceable(12345) %x)
+
+define internal fastcc void @foo(i32* %x) {
+entry:
+  %arrayidx = getelementptr inbounds i32, i32* %x, i64 5
+  store i32 10, i32* %arrayidx, align 4
+  tail call void @goo(i32* %x)
+  ret void
+}
+
+declare void @goo(i32*)

test/Transforms/FunctionAttrs/internal_noalias.ll

+; RUN: opt -S -functionattrs -mem2reg -functionattrs < %s | FileCheck %s
+;
+; Check that we derive noalias attributes for the arguments of the
+; noalias_args_argmem function from its call sites.
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; Function Attrs: noinline nounwind uwtable
+define dso_local i32 @visible(i32* noalias %A, i32* noalias %B) #0 {
+entry:
+  %call1 = call i32 @noalias_args(i32* %A, i32* %B)
+  %call2 = call i32 @noalias_args_argmem(i32* %A, i32* %B)
+  %add = add nsw i32 %call1, %call2
+  ret i32 %add
+}
+
+; CHECK: define internal i32 @noalias_args(i32* noalias nocapture nonnull readonly dereferenceable(4) %A, i32* noalias nocapture nonnull readonly dereferenceable(4) %B)
+;
+; Function Attrs: noinline nounwind uwtable
+define internal i32 @noalias_args(i32* %A, i32* %B) #0 {
+entry:
+  %0 = load i32, i32* %A, align 4
+  %1 = load i32, i32* %B, align 4
+  %add = add nsw i32 %0, %1
+  %call = call i32 @noalias_args_argmem(i32* %A, i32* %B)
+  %add2 = add nsw i32 %add, %call
+  ret i32 %add2
+}
+
+; CHECK: define internal i32 @noalias_args_argmem(i32* noalias nocapture nonnull readonly dereferenceable(4) %A, i32* noalias nocapture nonnull readonly dereferenceable(4) %B)
+;
+; Function Attrs: noinline nounwind uwtable
+define internal i32 @noalias_args_argmem(i32* %A, i32* %B) #1 {
+entry:
+  %0 = load i32, i32* %A, align 4
+  %1 = load i32, i32* %B, align 4
+  %add = add nsw i32 %0, %1
+  ret i32 %add
+}
+
+; Function Attrs: noinline nounwind uwtable
+define dso_local i32 @visible_local(i32* %A) #0 {
+entry:
+  %B = alloca i32, align 4
+  store i32 5, i32* %B, align 4
+  %call1 = call i32 @noalias_args(i32* %A, i32* nonnull %B)
+  %call2 = call i32 @noalias_args_argmem(i32* %A, i32* nonnull %B)
+  %add = add nsw i32 %call1, %call2
+  ret i32 %add
+}
+
+attributes #0 = { noinline nounwind uwtable }
+attributes #1 = { argmemonly noinline nounwind uwtable }

test/Transforms/FunctionAttrs/naked_functions.ll

 ; RUN: opt -S -functionattrs %s | FileCheck %s
 ; RUN: opt -S -passes='function-attrs' %s | FileCheck %s
 
 ; Don't change the attributes of parameters of naked functions, in particular
 ; don't mark them as readnone
 
 @g = common global i32 0, align 4
 
 define i32 @bar() {
 entry:
   %call = call i32 @foo(i32* @g)
-; CHECK: %call = call i32 @foo(i32* @g)
+; CHECK: %call = call i32 @foo(i32* nonnull @g)
   ret i32 %call
 }
 
 define internal i32 @foo(i32*) #0 {
 entry:
   %retval = alloca i32, align 4
   call void asm sideeffect "ldr r0, [r0] \0Abx lr        \0A", ""()
   unreachable
 }
 
 ; CHECK: define internal i32 @foo(i32*)
 
 attributes #0 = { naked }

test/Transforms/FunctionAttrs/noalias_phi.ll

+; RUN: opt -S -functionattrs < %s | FileCheck %s
+;
+;    int *foo(int Off, int N) {
+;      int *A = malloc(N);
+;      while (Off-- > 0)
+;        *(A++) = Off;
+;      return A;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; CHECK: define dso_local noalias i32* @foo(i32 %Off, i32 %N) {
+define dso_local i32* @foo(i32 %Off, i32 %N) {
+entry:
+  %conv = sext i32 %N to i64
+  %call = call i8* @malloc(i64 %conv)
+  %tmp = bitcast i8* %call to i32*
+  br label %while.cond
+
+while.cond:                                       ; preds = %while.body, %entry
+  %A.0 = phi i32* [ %tmp, %entry ], [ %incdec.ptr, %while.body ]
+  %Off.addr.0 = phi i32 [ %Off, %entry ], [ %dec, %while.body ]
+  %dec = add nsw i32 %Off.addr.0, -1
+  %cmp = icmp sgt i32 %Off.addr.0, 0
+  br i1 %cmp, label %while.body, label %while.end
+
+while.body:                                       ; preds = %while.cond
+  %incdec.ptr = getelementptr inbounds i32, i32* %A.0, i64 1
+  store i32 %dec, i32* %A.0, align 4
+  br label %while.cond
+
+while.end:                                        ; preds = %while.cond
+  %A.0.lcssa = phi i32* [ %A.0, %while.cond ]
+  ret i32* %A.0.lcssa
+}
+
+declare dso_local noalias i8* @malloc(i64)
+
+
+; CHECK: define dso_local noalias i32* @bar(i32 %Off, i32 %N) {
+define dso_local i32* @bar(i32 %Off, i32 %N) {
+entry:
+  %conv = sext i32 %N to i64
+  %call = call noalias i8* @mymalloc(i64 %conv)
+  %tmp = bitcast i8* %call to i32*
+  br label %while.cond
+
+while.cond:                                       ; preds = %while.body, %entry
+  %A.0 = phi i32* [ %tmp, %entry ], [ %incdec.ptr, %while.body ]
+  %Off.addr.0 = phi i32 [ %Off, %entry ], [ %dec, %while.body ]
+  %dec = add nsw i32 %Off.addr.0, -1
+  %cmp = icmp sgt i32 %Off.addr.0, 0
+  br i1 %cmp, label %while.body, label %while.end
+
+while.body:                                       ; preds = %while.cond
+  %incdec.ptr = getelementptr inbounds i32, i32* %A.0, i64 1
+  store i32 %dec, i32* %A.0, align 4
+  br label %while.cond
+
+while.end:                                        ; preds = %while.cond
+  %A.0.lcssa = phi i32* [ %A.0, %while.cond ]
+  ret i32* %A.0.lcssa
+}
+
+declare dso_local i8* @mymalloc(i64)

test/Transforms/FunctionAttrs/nonnull-global.ll

 ; RUN: opt -S -functionattrs %s | FileCheck %s
 ; RUN: opt -S -passes=function-attrs %s | FileCheck %s
 
+; Note that @a might be at address '0', according to the !absolute_symbol
+; metadata, _but_ only in @bar this is actually allowed. In @foo, null is
+; not a valid pointer to be referenced while @a has to be a dereferenceable
+; address. Thus, for @foo we derive the return attribute nonnull and for
+; @bar we won't.
+
 @a = external global i8, !absolute_symbol !0
 
-; CHECK-NOT: define nonnull
+; CHECK: define nonnull dereferenceable(1)
 define i8* @foo() {
   ret i8* @a
 }
 
+; CHECK: define dereferenceable_or_null(1)
+; CHECK-NOT: nonnull
+define i8* @bar() #0 {
+  ret i8* @a
+}
+
+attributes #0 = { "null-pointer-is-valid"="true" }
+
 !0 = !{i64 0, i64 256}

test/Transforms/FunctionAttrs/nonnull.ll

 define i8* @test2(i8* nonnull %p) {
 ; CHECK: define nonnull i8* @test2
   ret i8* %p
 }
 
 ; Given an SCC where one of the functions can not be marked nonnull,
 ; can we still mark the other one which is trivially nonnull
 define i8* @scc_binder() {
-; CHECK: define i8* @scc_binder
+; CHECK: define noalias i8* @scc_binder
   call i8* @test3()
   ret i8* null
 }
 
 define i8* @test3() {
 ; CHECK: define nonnull i8* @test3
   call i8* @scc_binder()
   %ret = call i8* @ret_nonnull()
   ret i8* %ret
 }
 
 ; Given a mutual recursive set of functions, we can mark them
 ; nonnull if neither can ever return null.  (In this case, they
 ; just never return period.)
 define i8* @test4_helper() {
-; CHECK: define noalias nonnull i8* @test4_helper
+; CHECK: define noalias nonnull dereferenceable(1073741824) i8* @test4_helper
   %ret = call i8* @test4()
   ret i8* %ret
 }
 
 define i8* @test4() {
-; CHECK: define noalias nonnull i8* @test4
+; CHECK: define noalias nonnull dereferenceable(1073741824) i8* @test4
   %ret = call i8* @test4_helper()
   ret i8* %ret
 }
 
 ; Given a mutual recursive set of functions which *can* return null
 ; make sure we haven't marked them as nonnull.
 define i8* @test5_helper() {
 ; CHECK: define noalias i8* @test5_helper

 
 declare i8 @use1safecall(i8* %x) readonly nounwind ; readonly+nounwind guarantees that execution continues to successor
 
 ; Can't extend non-null to parent for any argument because the 2nd call is not guaranteed to execute.
 
 define void @parent1(i8* %a, i8* %b, i8* %c) {
 ; CHECK-LABEL: @parent1(i8* %a, i8* %b, i8* %c)
 ; CHECK-NEXT:    call void @use3(i8* %c, i8* %a, i8* %b)
-; CHECK-NEXT:    call void @use3nonnull(i8* %b, i8* %c, i8* %a)
+; CHECK-NEXT:    call void @use3nonnull(i8* nonnull %b, i8* nonnull %c, i8* nonnull %a)
 ; CHECK-NEXT:    ret void
 ;
   call void @use3(i8* %c, i8* %a, i8* %b)
   call void @use3nonnull(i8* %b, i8* %c, i8* %a)
   ret void
 }
 
 ; Extend non-null to parent for all arguments.
 
 define void @parent2(i8* %a, i8* %b, i8* %c) {
 ; CHECK-LABEL: @parent2(i8* nonnull %a, i8* nonnull %b, i8* nonnull %c)
-; CHECK-NEXT:    call void @use3nonnull(i8* %b, i8* %c, i8* %a)
-; CHECK-NEXT:    call void @use3(i8* %c, i8* %a, i8* %b)
+; CHECK-NEXT:    call void @use3nonnull(i8* nonnull %b, i8* nonnull %c, i8* nonnull %a)
+; CHECK-NEXT:    call void @use3(i8* nonnull %c, i8* nonnull %a, i8* nonnull %b)
 ; CHECK-NEXT:    ret void
 ;
   call void @use3nonnull(i8* %b, i8* %c, i8* %a)
   call void @use3(i8* %c, i8* %a, i8* %b)
   ret void
 }
 
 ; Extend non-null to parent for 1st argument.
 
 define void @parent3(i8* %a, i8* %b, i8* %c) {
 ; CHECK-LABEL: @parent3(i8* nonnull %a, i8* %b, i8* %c)
-; CHECK-NEXT:    call void @use1nonnull(i8* %a)
-; CHECK-NEXT:    call void @use3(i8* %c, i8* %b, i8* %a)
+; CHECK-NEXT:    call void @use1nonnull(i8* nonnull %a)
+; CHECK-NEXT:    call void @use3(i8* %c, i8* %b, i8* nonnull %a)
 ; CHECK-NEXT:    ret void
 ;
   call void @use1nonnull(i8* %a)
   call void @use3(i8* %c, i8* %b, i8* %a)
   ret void
 }
 
 ; Extend non-null to parent for last 2 arguments.
 
 define void @parent4(i8* %a, i8* %b, i8* %c) {
 ; CHECK-LABEL: @parent4(i8* %a, i8* nonnull %b, i8* nonnull %c)
-; CHECK-NEXT:    call void @use2nonnull(i8* %c, i8* %b)
-; CHECK-NEXT:    call void @use2(i8* %a, i8* %c)
-; CHECK-NEXT:    call void @use1(i8* %b)
+; CHECK-NEXT:    call void @use2nonnull(i8* nonnull %c, i8* nonnull %b)
+; CHECK-NEXT:    call void @use2(i8* %a, i8* nonnull %c)
+; CHECK-NEXT:    call void @use1(i8* nonnull %b)
 ; CHECK-NEXT:    ret void
 ;
   call void @use2nonnull(i8* %c, i8* %b)
   call void @use2(i8* %a, i8* %c)
   call void @use1(i8* %b)
   ret void
 }
 
 ; The callsite must execute in order for the attribute to transfer to the parent.
 ; It appears benign to extend non-null to the parent in this case, but we can't do that
 ; because it would incorrectly propagate the wrong information to its callers.
 
 define void @parent5(i8* %a, i1 %a_is_notnull) {
 ; CHECK-LABEL: @parent5(i8* %a, i1 %a_is_notnull)
 ; CHECK-NEXT:    br i1 %a_is_notnull, label %t, label %f
 ; CHECK:       t:
-; CHECK-NEXT:    call void @use1nonnull(i8* %a)
+; CHECK-NEXT:    call void @use1nonnull(i8* nonnull %a)
 ; CHECK-NEXT:    ret void
 ; CHECK:       f:
 ; CHECK-NEXT:    ret void
 ;
   br i1 %a_is_notnull, label %t, label %f
 t:
   call void @use1nonnull(i8* %a)
   ret void
 f:
   ret void
 }
 
 ; The callsite must execute in order for the attribute to transfer to the parent.
 ; The volatile load might trap, so there's no guarantee that we'll ever get to the call.
 
 define i8 @parent6(i8* %a, i8* %b) {
 ; CHECK-LABEL: @parent6(i8* %a, i8* %b)
 ; CHECK-NEXT:    [[C:%.*]] = load volatile i8, i8* %b
-; CHECK-NEXT:    call void @use1nonnull(i8* %a)
+; CHECK-NEXT:    call void @use1nonnull(i8* nonnull %a)
 ; CHECK-NEXT:    ret i8 [[C]]
 ;
   %c = load volatile i8, i8* %b
   call void @use1nonnull(i8* %a)
   ret i8 %c
 }
 
 ; The nonnull callsite is guaranteed to execute, so the argument must be nonnull throughout the parent.
 
 define i8 @parent7(i8* %a) {
 ; CHECK-LABEL: @parent7(i8* nonnull %a)
-; CHECK-NEXT:    [[RET:%.*]] = call i8 @use1safecall(i8* %a)
-; CHECK-NEXT:    call void @use1nonnull(i8* %a)
+; CHECK-NEXT:    [[RET:%.*]] = call i8 @use1safecall(i8* nonnull %a)
+; CHECK-NEXT:    call void @use1nonnull(i8* nonnull %a)
 ; CHECK-NEXT:    ret i8 [[RET]]
 ;
   %ret = call i8 @use1safecall(i8* %a)
   call void @use1nonnull(i8* %a)
   ret i8 %ret
 }
 
 ; Make sure that an invoke works similarly to a call.
 
 declare i32 @esfp(...)
 
 define i1 @parent8(i8* %a, i8* %bogus1, i8* %b) personality i8* bitcast (i32 (...)* @esfp to i8*){
 ; CHECK-LABEL: @parent8(i8* nonnull %a, i8* nocapture readnone %bogus1, i8* nonnull %b)
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    invoke void @use2nonnull(i8* %a, i8* %b)
+; CHECK-NEXT:    invoke void @use2nonnull(i8* nonnull %a, i8* nonnull %b)
 ; CHECK-NEXT:    to label %cont unwind label %exc
 ; CHECK:       cont:
 ; CHECK-NEXT:    [[NULL_CHECK:%.*]] = icmp eq i8* %b, null
 ; CHECK-NEXT:    ret i1 [[NULL_CHECK]]
 ; CHECK:       exc:
 ; CHECK-NEXT:    [[LP:%.*]] = landingpad { i8*, i32 }
 ; CHECK-NEXT:    filter [0 x i8*] zeroinitializer
 ; CHECK-NEXT:    unreachable

 }
 
 ; CHECK: define i32 addrspace(3)* @gep2(
 define i32 addrspace(3)* @gep2(i32 addrspace(3)* %p) {
   %q = getelementptr inbounds i32, i32 addrspace(3)* %p, i32 1
   ret i32 addrspace(3)* %q
 }
 
+
+declare i8* @strrchr(i8*, i32)
+
+define internal fastcc nonnull i8* @select(i8* nonnull readonly %str) unnamed_addr #3 {
+entry:
+  %call = call i8* @strrchr(i8* %str, i32 47) #8
+  %tobool = icmp eq i8* %call, null
+  %add.ptr = getelementptr inbounds i8, i8* %call, i64 1
+  %cond = select i1 %tobool, i8* %str, i8* %add.ptr
+  ret i8* %cond
+}
+
 attributes #0 = { "null-pointer-is-valid"="true" }

test/Transforms/FunctionAttrs/readattrs.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt < %s -functionattrs -S | FileCheck %s
+; RUN: opt < %s -functionattrs -mem2reg -functionattrs -S | FileCheck %s
 ; RUN: opt < %s -aa-pipeline=basic-aa -passes='cgscc(function-attrs)' -S | FileCheck %s
 @x = global i32 0
 
 declare void @test1_1(i8* %x1_1, i8* readonly %y1_1, ...)
 
 ; CHECK: define void @test1_2(i8* %x1_2, i8* readonly %y1_2, i8* %z1_2)
 define void @test1_2(i8* %x1_2, i8* %y1_2, i8* %z1_2) {
   call void (i8*, i8*, ...) @test1_1(i8* %x1_2, i8* %y1_2, i8* %z1_2)

 declare void @test4_1(i8* nocapture) readonly
 
 ; CHECK: define void @test4_2(i8* nocapture readonly %p)
 define void @test4_2(i8* %p) {
   call void @test4_1(i8* %p)
   ret void
 }
 
-; CHECK: define void @test5(i8** nocapture %p, i8* %q)
+; CHECK: define void @test5(i8** nocapture nonnull dereferenceable(8) %p, i8* %q)
 ; Missed optz'n: we could make %q readnone, but don't break test6!
 define void @test5(i8** %p, i8* %q) {
   store i8* %q, i8** %p
   ret void
 }
 
 declare void @test6_1()
-; CHECK: define void @test6_2(i8** nocapture %p, i8* %q)
+; CHECK: define void @test6_2(i8** nocapture nonnull dereferenceable(8) %p, i8* %q)
 ; This is not a missed optz'n.
 define void @test6_2(i8** %p, i8* %q) {
   store i8* %q, i8** %p
   call void @test6_1()
   ret void
 }
 
 ; CHECK: define void @test7_1(i32* inalloca nocapture %a)
 ; inalloca parameters are always considered written
 define void @test7_1(i32* inalloca %a) {
   ret void
 }
 
 ; CHECK: define i32* @test8_1(i32* readnone returned %p)
 define i32* @test8_1(i32* %p) {
 entry:
   ret i32* %p
 }
 
-; CHECK: define void @test8_2(i32* %p)
+; CHECK: define void @test8_2(i32* nonnull dereferenceable(4) %p)
 define void @test8_2(i32* %p) {
 entry:
   %call = call i32* @test8_1(i32* %p)
   store i32 10, i32* %call, align 4
   ret void
 }
 
 ; CHECK: declare void @llvm.masked.scatter

test/Transforms/FunctionAttrs/recursion_and_phi.ll

+; RUN: opt -S -functionattrs %s | FileCheck %s
+; RUN: opt -S -passes=function-attrs %s | FileCheck %s
+
+%struct.splay_node = type { i64, i64, %struct.splay_node*, %struct.splay_node* }
+
+; CHECK: define dso_local nonnull dereferenceable(8) %struct.splay_node* @find(%struct.splay_node* nonnull readonly dereferenceable(8) %root, i64 %key) local_unnamed_addr #0 {
+define dso_local %struct.splay_node* @find(%struct.splay_node* readonly %root, i64 %key) local_unnamed_addr #0 {
+entry:
+  %key1 = getelementptr inbounds %struct.splay_node, %struct.splay_node* %root, i64 0, i32 0
+  %0 = load i64, i64* %key1, align 8
+  %cmp = icmp slt i64 %0, %key
+  br i1 %cmp, label %land.lhs.true, label %if.else
+
+land.lhs.true:                                    ; preds = %entry
+  %right = getelementptr inbounds %struct.splay_node, %struct.splay_node* %root, i64 0, i32 3
+  %1 = load %struct.splay_node*, %struct.splay_node** %right, align 8
+  %cmp2 = icmp eq %struct.splay_node* %1, null
+  br i1 %cmp2, label %if.else, label %if.then
+
+if.then:                                          ; preds = %land.lhs.true
+  %call = call %struct.splay_node* @find(%struct.splay_node* %1, i64 %key)
+  br label %return
+
+if.else:                                          ; preds = %land.lhs.true, %entry
+  %2 = load i64, i64* %key1, align 8
+  %cmp6 = icmp sgt i64 %2, %key
+  br i1 %cmp6, label %land.lhs.true7, label %return
+
+land.lhs.true7:                                   ; preds = %if.else
+  %left = getelementptr inbounds %struct.splay_node, %struct.splay_node* %root, i64 0, i32 2
+  %3 = load %struct.splay_node*, %struct.splay_node** %left, align 8
+  %cmp8 = icmp eq %struct.splay_node* %3, null
+  br i1 %cmp8, label %return, label %if.then9
+
+if.then9:                                         ; preds = %land.lhs.true7
+  %call11 = call %struct.splay_node* @find(%struct.splay_node* %3, i64 %key)
+  br label %return
+
+return:                                           ; preds = %if.else, %land.lhs.true7, %if.then9, %if.then
+  %retval.0 = phi %struct.splay_node* [ %call, %if.then ], [ %call11, %if.then9 ], [ %root, %land.lhs.true7 ], [ %root, %if.else ]
+  ret %struct.splay_node* %retval.0
+}
+

test/Transforms/FunctionAttrs/sql_malloc.ll

+; RUN: opt -S -functionattrs < %s | FileCheck %s
+
+declare noalias i8* @malloc(i64)
+@mem.0 = common global i64 0, align 4
+@mem.1 = common global void (i8*, i64, i32)* null, align 4
+@mem.2 = common global i8* null, align 4
+@mem.3 = common global i1 0, align 4
+@mem.4 = common global i64* null, align 4
+@mem.5 = common global i64 0, align 4
+@mem.6 = common global i64 0, align 4
+
+; CHECK: define dso_local noalias i8* @sqlite3_malloc(i32 %nBytes)
+define dso_local i8* @sqlite3_malloc(i32 %nBytes) {
+entry:
+  %cmp = icmp sgt i32 %nBytes, 0
+  br i1 %cmp, label %if.then, label %if.end23
+
+if.then:                                          ; preds = %entry
+  %0 = load i64*, i64** @mem.4, align 8
+  %cmp.i = icmp eq i64* %0, null
+  br i1 %cmp.i, label %if.then.i, label %enterMem.exit
+
+if.then.i:                                        ; preds = %if.then
+  store i64* inttoptr (i64 8 to i64*), i64** @mem.4, align 8
+  br label %enterMem.exit
+
+enterMem.exit:                                    ; preds = %if.then, %if.then.i
+  %1 = load void (i8*, i64, i32)*, void (i8*, i64, i32)** @mem.1, align 8
+  %cmp1 = icmp eq void (i8*, i64, i32)* %1, null
+  br i1 %cmp1, label %if.end, label %land.lhs.true
+
+land.lhs.true:                                    ; preds = %enterMem.exit
+  %2 = load i64, i64* @mem.5, align 8
+  %conv = sext i32 %nBytes to i64
+  %add = add nsw i64 %2, %conv
+  %3 = load i64, i64* @mem.0, align 8
+  %cmp2 = icmp slt i64 %add, %3
+  br i1 %cmp2, label %if.end, label %if.then4
+
+if.then4:                                         ; preds = %land.lhs.true
+  %.b.i38 = load i1, i1* @mem.3, align 8
+  br i1 %.b.i38, label %if.end, label %if.end.i40
+
+if.end.i40:                                       ; preds = %if.then4
+  store i1 true, i1* @mem.3, align 8
+  %4 = load i8*, i8** @mem.2, align 8
+  tail call void %1(i8* %4, i64 %2, i32 %nBytes) #6
+  store i1 false, i1* @mem.3, align 8
+  br label %if.end
+
+if.end:                                           ; preds = %if.end.i40, %if.then4, %land.lhs.true, %enterMem.exit
+  %add5 = add nsw i32 %nBytes, 8
+  %conv6 = sext i32 %add5 to i64
+  %call = tail call noalias i8* @malloc(i64 %conv6) #6
+  %cmp7 = icmp eq i8* %call, null
+  br i1 %cmp7, label %if.then9, label %if.then14
+
+if.then9:                                         ; preds = %if.end
+  %5 = load void (i8*, i64, i32)*, void (i8*, i64, i32)** @mem.1, align 8
+  %cmp.i36 = icmp eq void (i8*, i64, i32)* %5, null
+  %.b.i = load i1, i1* @mem.3, align 8
+  %or.cond.i = or i1 %cmp.i36, %.b.i
+  br i1 %or.cond.i, label %if.end13, label %if.end.i
+
+if.end.i:                                         ; preds = %if.then9
+  store i1 true, i1* @mem.3, align 8
+  %6 = load i64, i64* @mem.5, align 8
+  %7 = load i8*, i8** @mem.2, align 8
+  tail call void %5(i8* %7, i64 %6, i32 %nBytes) #6
+  store i1 false, i1* @mem.3, align 8
+  br label %if.end13
+
+if.end13:                                         ; preds = %if.end.i, %if.then9
+  %call12 = tail call noalias i8* @malloc(i64 %conv6) #6
+  %tobool = icmp eq i8* %call12, null
+  br i1 %tobool, label %if.end23, label %if.then14
+
+if.then14:                                        ; preds = %if.end, %if.end13
+  %p.0.in43 = phi i8* [ %call12, %if.end13 ], [ %call, %if.end ]
+  %p.0 = bitcast i8* %p.0.in43 to i64*
+  %conv15 = sext i32 %nBytes to i64
+  store i64 %conv15, i64* %p.0, align 8
+  %incdec.ptr = getelementptr inbounds i8, i8* %p.0.in43, i64 8
+  %8 = load i64, i64* @mem.5, align 8
+  %add17 = add nsw i64 %8, %conv15
+  store i64 %add17, i64* @mem.5, align 8
+  %9 = load i64, i64* @mem.6, align 8
+  %cmp18 = icmp sgt i64 %add17, %9
+  br i1 %cmp18, label %if.then20, label %if.end23
+
+if.then20:                                        ; preds = %if.then14
+  store i64 %add17, i64* @mem.6, align 8
+  br label %if.end23
+
+if.end23:                                         ; preds = %if.end13, %if.then20, %if.then14, %entry
+  %10 = phi i8* [ %incdec.ptr, %if.then20 ], [ %incdec.ptr, %if.then14 ], [ null, %if.end13 ], [ null, %entry ]
+  ret i8* %10
+}
+

test/Transforms/Inline/delete-call.ll

 ; REQUIRES: asserts
 ; RUN: opt -S -inline -stats < %s 2>&1 | FileCheck %s
 ; CHECK: Number of functions inlined
 
-; RUN: opt -S -inline -functionattrs -stats < %s 2>&1 | FileCheck -check-prefix=CHECK-FUNCTIONATTRS %s
+; RUN: opt -S -functionattrs -inline -stats < %s 2>&1 | FileCheck -check-prefix=CHECK-FUNCTIONATTRS %s
 ; CHECK-FUNCTIONATTRS: Number of call sites deleted, not inlined
 
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128-n8:16:32"
 target triple = "i386-apple-darwin9.8"
 
 define internal i32 @test(i32 %x, i32 %y, i32 %z) nounwind {
 entry:
   %0 = add nsw i32 %y, %z                         ; <i32> [#uses=1]

test/Transforms/Reassociate/reassociate-deadinst.ll

-; RUN: opt < %s -inline -functionattrs -reassociate -S | FileCheck %s
+; RUN: opt < %s -functionattrs -inline -reassociate -S | FileCheck %s
 
 ; CHECK-NOT: func1
 ; CHECK-LABEL: main
 ; CHECK-NEXT: ret void
 
 define internal i16 @func1() noinline #0 {
   ret i16 0
 }
 
 define void @main(i16 %argc, i16** %argv) #0 {
   %_tmp0 = call i16 @func1()
   %_tmp2 = zext i16 %_tmp0 to i32
   ret void
 }
 attributes #0 = { minsize nounwind optsize }