[FunctionAttrs] Annotate function arguments with call site information

[jdoerfert]

Summary

If a function is internal and all call sites are statically known, we can
try to derive attributes for the arguments. With this patch we introduce
this attribute deduction for the following attributes:

• non-null
• no-capture
• read-none
• read-only
• write-only
• no-alias
• alignment
• dereferencable
• dereferencable_or_null

Note that many internal functions are inlined, but some are not. This
could be caused by size constrains, recursion, or because the internal
function is used as a "callback", thus an indirect call that might or
might not be visible in the current module. While this patch does not
require callback calls to be identified, it is especially designed to
allow them later on. One type of callback that can significantly benefit
from proper attribute deduction are outlined functions passed to OpenMP
runtime calls. Though, in practice we see various kinds of callbacks
including user defined higher-order functions and calls to builtins like
qsort.

Note that this patch should be a generalization of D4609.

[jdoerfert]

Fixed spelling, stripped casts, added the tests from D4609

[jdoerfert]

Remove large macro in favor of a switch

[jdoerfert]

Use call sites for now and improve testing of non-null deduction

[jdoerfert]

lib/Transforms/IPO/FunctionAttrs.cpp

1196

Here we need to check NullPointerIsDefined too.

[jdoerfert]

This is a pre-Attributor patch. Though, some logic and tests might be salvaged.

lib/Transforms/IPO/FunctionAttrs.cpp

 #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/Metadata.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/Type.h"

 #include <vector>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "functionattrs"
 
 STATISTIC(NumReadNone, "Number of functions marked readnone");
 STATISTIC(NumReadOnly, "Number of functions marked readonly");
-STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
 STATISTIC(NumReturned, "Number of arguments marked returned");
+STATISTIC(NumNoCaptureArg, "Number of arguments marked nocapture");
 STATISTIC(NumReadNoneArg, "Number of arguments marked readnone");
 STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly");
+STATISTIC(NumWriteOnlyArg, "Number of arguments marked writeonly");
+STATISTIC(NumNonNullArg, "Number of arguments marked nonnull");
+STATISTIC(NumAlignmentArg,
+          "Number of arguments marked with alignment information");
+STATISTIC(NumDereferenceableArg,
+          "Number of arguments marked as dereferenceable");
+STATISTIC(NumDereferenceableOrNullArg,
+          "Number of arguments marked as dereferenceable or null");
+STATISTIC(NumNoAliasArg, "Number of arguments marked noalias");
 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(NumFunctionsWithStaticCallSites,
+          "Number of functions with statically known call sites");
+STATISTIC(NumSCCsWithStaticCallSites,
+          "Number of SCCs with statically known call sites");
+
 // 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<bool> DisableCalleeArgumentAttrInference(
+    "disable-callee-arg-attr-inference", cl::Hidden,
+    cl::desc("Do not infer callee argument attributes from call sites"));
+
 namespace {
 
 using SCCNodeSet = SmallSetVector<Function *, 8>;
 
 } // end anonymous namespace
 
 /// Returns the memory access attribute for function F using AAR for AA results,
 /// where SCCNodes is the current SCC.
while (!Worklist.empty()) {
     default:
       return Attribute::None;
     }
   }
 
   return IsRead ? Attribute::ReadOnly : Attribute::ReadNone;
 }
 
+/// Definition of parameter attributes we want to propagate from call sites
+/// (direct and callback) to a callee. This macro construct allows us to
+/// minimize explicit code duplication. The properties we define here are the
+/// following:
+///  - NAME: to identify the attribute.
+///  - KIND: to interact with other parts of LLVM (Attribute::AttrKind).
+///  - INIT: initial value associated with this attribute.
+#define ABSTRACT_ARGUMENT_ATTRIBUTES()                                         \
+  ABSTRACT_ARGUMENT_ATTR_FUNC(NonNull, Attribute::NonNull, true)               \
+  ABSTRACT_ARGUMENT_ATTR_FUNC(NoCapture, Attribute::NoCapture, true)           \
+  ABSTRACT_ARGUMENT_ATTR_FUNC(ReadNone, Attribute::ReadNone, true)             \
+  ABSTRACT_ARGUMENT_ATTR_FUNC(ReadOnly, Attribute::ReadOnly, true)             \
+  ABSTRACT_ARGUMENT_ATTR_FUNC(WriteOnly, Attribute::WriteOnly, true)           \
+  ABSTRACT_ARGUMENT_ATTR_FUNC(NoAlias, Attribute::NoAlias, true)               \
+  ABSTRACT_ARGUMENT_ATTR_FUNC(Alignment, Attribute::Alignment, 0x40000000u)    \
+  ABSTRACT_ARGUMENT_ATTR_FUNC(Dereferenceable, Attribute::Dereferenceable,     \
+                              0x40000000u)                                     \
+  ABSTRACT_ARGUMENT_ATTR_FUNC(DereferenceableOrNull,                           \
+                              Attribute::DereferenceableOrNull, 0x40000000u)
+
+/// Helper data structure to manage parameter attributes.
+struct ArgumentAttributeSet {
+
+// Each attribute defined in the ABSTRACT_ARGUMENT_ATTRIBUTES macro above is
+// expanded to a member variable ("a_" + NAME + "_val") that cannot be accessed
+// directly but only through the generated getter and setter functions.
+#define ABSTRACT_ARGUMENT_ATTR_FUNC(NAME, KIND, INIT)                          \
+private:                                                                       \
+  decltype(INIT) a_##NAME##_val;                                               \
+                                                                               \
+public:                                                                        \
+  decltype(INIT) get##NAME##Attr() const { return a_##NAME##_val; }            \
+  bool has##NAME##Attr() const { return a_##NAME##_val; }                      \
+  void set##NAME##Attr(decltype(INIT) Val = INIT) { a_##NAME##_val = Val; }    \
+  void clear##NAME##Attr() { a_##NAME##_val = 0; }
+
+  ABSTRACT_ARGUMENT_ATTRIBUTES()
+#undef ABSTRACT_ARGUMENT_ATTR_FUNC
+
+  // Flag to simplify the check for any attribute. It is set by the clear()
+  // function and when hasAny() returns false.
+  bool HasAny = true;
+
+  // Check if any attribute is set.
+  bool hasAny() {
+    if (!HasAny)
+      return false;
+
+    bool Any = false;
+#define ABSTRACT_ARGUMENT_ATTR_FUNC(NAME, KIND, INIT) Any |= has##NAME##Attr();
+
+    ABSTRACT_ARGUMENT_ATTRIBUTES()
+#undef ABSTRACT_ARGUMENT_ATTR_FUNC
+    return HasAny = Any;
+  }
+
+  // Clear all attributes.
+  void clear() {
+    HasAny = false;
+#define ABSTRACT_ARGUMENT_ATTR_FUNC(NAME, KIND, INIT) clear##NAME##Attr();
+
+    ABSTRACT_ARGUMENT_ATTRIBUTES()
+#undef ABSTRACT_ARGUMENT_ATTR_FUNC
+  }
+};
+
+/// Wrapper around a function argument and the current abstract state expressed
+/// as a set of argument attributes. Note that access to the members is direct
+/// and the constructor will initialize the attribute set according to the given
+/// attribute (Arg).
+struct AbstractArgument {
+  // The argument this abstract argument represents.
+  Argument *Arg;
+
+  // The set of attributes for the argument Arg.
+  ArgumentAttributeSet Attrs;
+
+  // Simple constructor that initializes the attribute set according to the
+  // properties of @p Arg and its parent function.
+  AbstractArgument(Argument &Arg) : Arg(&Arg) {
+
+  // TODO: This might not set dereferenceability attributes if the parent
+  // returns a dereferenceable pointer!
+#define ABSTRACT_ARGUMENT_ATTR_FUNC(NAME, KIND, INIT)                          \
+  if (!Arg.hasAttribute(KIND) && !Arg.getParent()->hasFnAttribute(KIND))       \
+    Attrs.set##NAME##Attr();                                                   \
+  else                                                                         \
+    Attrs.clear##NAME##Attr();
+
+    ABSTRACT_ARGUMENT_ATTRIBUTES()
+#undef ABSTRACT_ARGUMENT_ATTR_FUNC
+  }
+};
+
+/// Helper function that lookup the abstract state for an attribute given an
+/// argument @p Arg, the attribute kind, and a abstract state relation for the
+/// SCC. It returns the current value of the abstract argument associated with
+/// @p Arg, if there is any. If not, the boolean @p Found is set to false.
+template <typename FunctionPointerArgumentsMapTy>
+static uint64_t getAbstractArgumentValue(
+    Argument *Arg, Attribute::AttrKind Kind, bool &Found,
+    FunctionPointerArgumentsMapTy &FunctionPointerArgumentsMap) {
+  Found = false;
+  // If the argument is null or its parent is not in the current SCC,
+  // return zero and indicate that the abstract attribute was not found.
+  if (!Arg)
+    return 0;
+  auto It = FunctionPointerArgumentsMap.find(Arg->getParent());
+  if (It == FunctionPointerArgumentsMap.end())
+    return 0;
+
+  Found = true;
+  for (AbstractArgument &AA : It->second)
+    if (AA.Arg == Arg) {
+      switch (Kind) {
+#define ABSTRACT_ARGUMENT_ATTR_FUNC(NAME, KIND, INIT)                          \
+  case KIND:                                                                   \
+    return AA.Attrs.get##NAME##Attr();
+
+        ABSTRACT_ARGUMENT_ATTRIBUTES()
+#undef ABSTRACT_ARGUMENT_ATTR_FUNC
+
+      default:
+        llvm_unreachable("Attribute kind is not supported here!\n");
+      }
+    }
+  llvm_unreachable("Argument was not mapped to an abstract argument!\n");
+}
+
+/// Helper function that only return true if the abstract value associated with
+/// @p Arg exists and the attribute in question is set.
+template <typename FunctionPointerArgumentsMapTy>
+static bool isValidAbstractArgument(
+    Argument *Arg, Attribute::AttrKind Kind,
+    FunctionPointerArgumentsMapTy &FunctionPointerArgumentsMap) {
+  bool Found;
+  if (getAbstractArgumentValue(Arg, Kind, Found, FunctionPointerArgumentsMap))
+    return Found;
+  return false;
+}
+
+/// Helper to determine the dereferenceability of the parameter @p Param.
+/// Only if @p AllowNull is set, the parameter @p Param is allowed to be null.
+template <typename FunctionPointerArgumentsMapTy>
+static uint64_t getParameterDereferencability(
+    Value *Param, const DataLayout &DL, bool AllowNull,
+    FunctionPointerArgumentsMapTy &FunctionPointerArgumentsMap) {
+
+  // If the parameter is an argument we first try to determine the
+  // value based on the abstract state that might be mapped to it.
+  bool Found = false;
+  uint64_t Value = 0;
+  if (Argument *ParamArg = dyn_cast<Argument>(Param)) {
+    if (AllowNull)
+      Value =
+          getAbstractArgumentValue(ParamArg, Attribute::DereferenceableOrNull,
+                                   Found, FunctionPointerArgumentsMap);
+    else
+      Value = getAbstractArgumentValue(ParamArg, Attribute::Dereferenceable,
+                                       Found, FunctionPointerArgumentsMap);
+  }
+
+  // If a value was set, we cannot do better.
+  if (Found)
+    return Value;
+
+  // Otherwise, determine the dereferenceability explicitly.
+  //
+  // TODO: Figure out when we should add initial dereferenceable_or_null
+  //       attributes to allocation calls (malloc/calloc/realloc/...).
+
+  bool CanBeNull = false;
+  uint64_t DereferenceableBytes =
+      Param->getPointerDereferenceableBytes(DL, CanBeNull);
+  if (!CanBeNull)
+    return DereferenceableBytes;
+  return AllowNull ? DereferenceableBytes : 0;
+}
+
+/// Helper to determine the non-null property of the parameter @p Param.
+/// To this end, we check the abstract state of @p Arg in the SCC as well as
+/// the annotations of @p Param at the call sites.
+template <typename FunctionPointerArgumentsMapTy>
+static bool
+isNonNullParameter(CallSite &CS, Value *Param, Argument *ParamObjectArg,
+                   FunctionPointerArgumentsMapTy &FunctionPointerArgumentsMap) {
+  if (!EnableNonnullArgPropagation)
+    return false;
+
+  // First check if the parameter (Param) is actually an argument. If so, we
+  // check if it is marked as non-null or if the abstract state associated with
+  // that argument is.
+  if (ParamObjectArg &&
+      (ParamObjectArg->hasNonNullAttr() ||
+       isValidAbstractArgument(ParamObjectArg, Attribute::NonNull,
+                               FunctionPointerArgumentsMap)))
+    return true;
+
+  // If the above check failed, we look at the call site and check if the first
+  // occurence of the parameter (Param) has a non-null attribute.
+  unsigned NumArgs = CS.getNumArgOperands();
+  for (unsigned Idx = 0; Idx < NumArgs; Idx++)
+    if (CS.getArgOperand(Idx)->stripPointerCasts() == Param)
+      return CS.paramHasAttr(Idx, Attribute::NonNull);
+
+  llvm_unreachable("Parameter not found in call site!");
+}
+
+/// Helper to determine if the parameter @p Param is not aliasing with anything
+/// once assigned to the argument identified by the abstract argument @p AA.
+template <typename FunctionPointerArgumentsMapTy>
+static bool isValidNoAliasParameter(
+    AbstractArgument &AA, Value *Param, Argument *ParamObjectArg, CallSite &CS,
+    AAResults &AAR, const DominatorTree &DT,
+    FunctionPointerArgumentsMapTy &FunctionPointerArgumentsMap) {
+
+  // If ParamObjectArg (the underlying object of Param) is marked as
+  // no-alias, Param is no-alias in the context of the callee.
+  if (ParamObjectArg && ParamObjectArg->hasNoAliasAttr())
+    return true;
+
+  // If the callee only accesses memory accesible through the arguments we
+  // can skip the function local and captured checks and simply proceed to
+  // the alias check between the parameters.
+  if (!AAR.onlyAccessesArgPointees(
+          AAR.getModRefBehavior(AA.Arg->getParent()))) {
+
+    // Check if Param is function local in the caller context either explicitly
+    // or through the abstract state associated with it in the SCC. If not, we
+    // cannot conclude no-alias in the callee context.
+    bool IsFunctionLocal =
+        isIdentifiedFunctionLocal(Param) ||
+        isValidAbstractArgument(ParamObjectArg, Attribute::NoAlias,
+                                FunctionPointerArgumentsMap);
+    if (!IsFunctionLocal)
+      return false;
+
+    // We also conservatively require the parameter Param to be "uncaptured" in
+    // the caller up to the (callback) call.
+    Instruction *I = CS.getInstruction();
+    bool IsCapturedPtr =
+        PointerMayBeCapturedBefore(Param, false, true, I, &DT) &&
+        !isValidAbstractArgument(ParamObjectArg, Attribute::NoCapture,
+                                 FunctionPointerArgumentsMap);
+    if (IsCapturedPtr)
+      return false;
+  }
+
+  // If the callee only accesses memory through arguments, or the parameter
+  // (Param) is function local in the caller and not captured up to the call
+  // site, we still have to ensure there is no other pointer argument it (Param)
+  // could alias with. Only then the no-alias property holds in the callee.
+  unsigned NumArgs = CS.getNumArgOperands();
+  for (unsigned Idx = 0; Idx < NumArgs; Idx++) {
+    if (Idx == AA.Arg->getArgNo())
+      continue;
+    if (CS.paramHasAttr(Idx, Attribute::NoAlias))
+      continue;
+    if (!AAR.isNoAlias(Param, CS.getArgOperand(Idx)))
+      return false;
+  }
+
+  return true;
+}
+
+/// Transformer function that removes all invalid attributes from the abstract
+/// state of an argument in the SCC. It is executed for each abstract call site
+/// @p CS with the mapping from parameter @p Param in the caller to abstract
+/// argument @p AA in the callee.
+template <typename FunctionPointerArgumentsMapTy>
+static bool removeInvalidAttributes(
+    Value *Param, AbstractArgument &AA, CallSite &CS, const DataLayout &DL,
+    AAResults &AAR, const DominatorTree &DT,
+    FunctionPointerArgumentsMapTy &FunctionPointerArgumentsMap) {
+
+  // This should only be called if any attribute is set in the abstract state.
+  assert(AA.Attrs.hasAny() && "Cannot remove attributes since there are none!");
+
+  // If the parameter is not specified we clear all attributes.
+  if (!Param) {
+    AA.Attrs.clear();
+    return true;
+  }
+
+  // If a parameter was given we check all attributes that are currently set
+  // explicitly.
+  bool Changed = false;
+
+  // TODO: Even though the "ABSTRACT_ARGUMENT_ATTR_FUNC" macro is not that nice,
+  //       it often helped to write more concise code. However, in the following
+  //       we treat every attribute different and we should think about a
+  //       cleaner way to do this.
+  if (AA.Attrs.hasAlignmentAttr()) {
+    uint64_t ParameterAlignment = Param->getPointerAlignment(DL);
+
+    auto OldAlignment = AA.Attrs.getAlignmentAttr();
+    if (ParameterAlignment == 0) {
+      AA.Attrs.clearAlignmentAttr();
+    } else {
+      AA.Attrs.setAlignmentAttr(GreatestCommonDivisor64(
+          AA.Attrs.getAlignmentAttr(), ParameterAlignment));
+      if (AA.Attrs.getAlignmentAttr() == 1)
+        AA.Attrs.clearAlignmentAttr();
+    }
+    if (OldAlignment != AA.Attrs.getAlignmentAttr())
+      Changed = true;
+  }
+
+  if (AA.Attrs.hasDereferenceableAttr()) {
+    uint64_t ParameterDereferencability = getParameterDereferencability(
+        Param, DL, /* AllowNull */ false, FunctionPointerArgumentsMap);
+    if (AA.Attrs.getDereferenceableAttr() > ParameterDereferencability) {
+      AA.Attrs.setDereferenceableAttr(ParameterDereferencability);
+      Changed = true;
+    }
+  }
+
+  if (AA.Attrs.hasDereferenceableOrNullAttr()) {
+    uint64_t ParameterDereferencabilityOrNull = getParameterDereferencability(
+        Param, DL, /* AllowNull */ true, FunctionPointerArgumentsMap);
+    if (AA.Attrs.getDereferenceableOrNullAttr() >
+        ParameterDereferencabilityOrNull) {
+      AA.Attrs.setDereferenceableOrNullAttr(ParameterDereferencabilityOrNull);
+      Changed = true;
+    }
+  }
+
+  // Determine the function argument that is behind the parameter. Thus, this is
+  // only non-null if the parameter (Param) at the call site is actually a
+  // function argument of the calller.
+  Argument *ParamObjectArg = dyn_cast<Argument>(GetUnderlyingObject(Param, DL));
+
+  if (AA.Attrs.hasNonNullAttr()) {
+    if (!isNonNullParameter(CS, Param, ParamObjectArg,
+                            FunctionPointerArgumentsMap)) {
+      AA.Attrs.clearNonNullAttr();
+      Changed = true;
+    }
+  }
+
+  if (AA.Attrs.hasNoAliasAttr() &&
+      !isValidNoAliasParameter(AA, Param, ParamObjectArg, CS, AAR, DT,
+                               FunctionPointerArgumentsMap)) {
+    AA.Attrs.clearNoAliasAttr();
+    Changed = true;
+  }
+
+  if (AA.Attrs.hasNoCaptureAttr() &&
+      (!ParamObjectArg ||
+       (!ParamObjectArg->hasNoCaptureAttr() &&
+        !isValidAbstractArgument(ParamObjectArg, Attribute::NoCapture,
+                                 FunctionPointerArgumentsMap)))) {
+    AA.Attrs.clearNoCaptureAttr();
+    Changed = true;
+  }
+
+  if (AA.Attrs.hasReadNoneAttr() &&
+      (!ParamObjectArg ||
+       (!ParamObjectArg->hasAttribute(Attribute::ReadNone) &&
+        !AAR.doesNotAccessMemory(ParamObjectArg->getParent()) &&
+        !isValidAbstractArgument(ParamObjectArg, Attribute::ReadNone,
+                                 FunctionPointerArgumentsMap)))) {
+    AA.Attrs.clearReadNoneAttr();
+    Changed = true;
+  }
+
+  if (AA.Attrs.hasReadOnlyAttr() &&
+      (!ParamObjectArg ||
+       (!ParamObjectArg->hasAttribute(Attribute::ReadOnly) &&
+        !AAR.onlyReadsMemory(ParamObjectArg->getParent()) &&
+        !isValidAbstractArgument(ParamObjectArg, Attribute::ReadOnly,
+                                 FunctionPointerArgumentsMap)))) {
+    AA.Attrs.clearReadOnlyAttr();
+    Changed = true;
+  }
+
+  if (AA.Attrs.hasWriteOnlyAttr() &&
+      (!ParamObjectArg ||
+       (!ParamObjectArg->hasAttribute(Attribute::WriteOnly) &&
+        !AAR.doesNotReadMemory(
+            AAR.getModRefBehavior(ParamObjectArg->getParent())) &&
+        !isValidAbstractArgument(ParamObjectArg, Attribute::WriteOnly,
+                                 FunctionPointerArgumentsMap)))) {
+    AA.Attrs.clearWriteOnlyAttr();
+    Changed = true;
+  }
+
+  return Changed;
+}
+
+/// Helper to collect all direct and callback call sites of the functions in the
+/// SCC (@p SCCNodes). To reduce the number of analysis calls later, we collect
+/// all call sites of a function in @p FunctionCallSitesMap. The pointer
+/// arguments of these functions are, together with an initial abstract state,
+/// collected in the @p FunctionPointerArgumentsMap.
+template <typename SCCNodesTy, typename FunctionCallSitesMapTy,
+          typename FunctionPointerArgumentsMapTy>
+static void collectAllCallSites(
+    SCCNodesTy &SCCNodes, FunctionCallSitesMapTy &FunctionCallSitesMap,
+    FunctionPointerArgumentsMapTy &FunctionPointerArgumentsMap) {
+
+  // Get the container type used for abstract arguments.
+  using AbstractArgumentsTy = typename std::remove_reference<decltype(
+      FunctionPointerArgumentsMap[SCCNodes.front()])>::type;
+
+  for (Function *F : SCCNodes) {
+    // We derive attributes only for internal functions as we otherwise do not
+    // know all call sites.
+    if (!F->hasInternalLinkage()) {
+      // TODO: This is the point where we could think about deriving attributes
+      //       for the call sites despite outside callers and, if they seem
+      //       beneficial, we could duplicate the callee.
+      continue;
+    }
+
+    // If a function has internal linkage, we collect all pointer arguments.
+    AbstractArgumentsTy AbstractArguments;
+    for (Argument &Arg : F->args())
+      if (Arg.getType()->isPointerTy())
+        AbstractArguments.emplace_back(Arg);
+
+    // If no pointer arguments are present, the function does not need to be
+    // processed further. However, as with other potential problems checked for
+    // in the following, we do not give up on the SCC.
+    if (AbstractArguments.empty())
+      continue;
+
+    // In the next step we determine all direct and callback call sites for
+    // the function. To this end, we iterate over the uses and check if it is
+    // a direct call or potentially a callback call that we know about.
+    SmallVector<const Use *, 8> FUses;
+    for (const Use &FUse : F->uses())
+      FUses.push_back(&FUse);
+
+    bool OnlyValidUsers = true;
+    while (!FUses.empty()) {
+      const Use *FUse = FUses.pop_back_val();
+
+      // Casts are ignored but the uses are processed.
+      if (ConstantExpr *CE = dyn_cast<ConstantExpr>(FUse->get())) {
+        for (const Use &CEUse : CE->uses())
+          FUses.push_back(&CEUse);
+        continue;
+      }
+
+      Value *UserVal = FUse->getUser()->stripPointerCasts();
+      if (UserVal == F)
+        continue;
+
+      // We require a call site and a known called function for both, direct as
+      // well as callback calls.
+      CallSite CS(UserVal);
+
+      // TODO: Allow a bit cast of the called value here.
+      Function *CSCallee = CS ? CS.getCalledFunction() : nullptr;
+      if (!CSCallee) {
+        OnlyValidUsers = false;
+        break;
+      }
+
+      // Additionally, we require the caller code to be exactly what we will
+      // execute at runtime.
+      Function *Caller = CS.getCaller();
+      if (!Caller->hasExactDefinition()) {
+        OnlyValidUsers = false;
+        break;
+      }
+
+      // Next we determine the callback calls for this call site.
+      // TODO: The identification of callback calls is not part of the initial
+      //       patch that derives callee attributes from call sites.
+      //       Consequently, we assume no callback calls in the following.
+
+      // First handle direct calls and then callback calls. They are
+      // distinguished through the called function of the call site.
+      if (CSCallee == F) {
+
+        // For a direct call we additionally have to check that the callee is
+        // not also passed as an argument. We do this by checking that the use
+        // of the callee function (FUse) is actually the call site function
+        // argument.
+        if (!CS.isCallee(FUse)) {
+          OnlyValidUsers = false;
+          break;
+        }
+
+        // If the call is direct and the function use is the called function in
+        // the call site, we create an abstract call site. It is defined by the
+        // called function (CSCallee), the instruction that invokes it
+        // (CS.getInstruction()), and the parameters passed to the pointer
+        // arguments.
+        auto &CallSites = FunctionCallSitesMap[Caller];
+        CallSites.push_back(CS);
+
+        // Direct call is done, no need to check for a callback call.
+      } else {
+
+        // Callback calls are not yet supported.
+        OnlyValidUsers = false;
+        break;
+      }
+    }
+
+    // Only if all call sites of the function are valid, thus statically known,
+    // we can derive information from them. If not, we simply do not add the
+    // function to the FunctionPointerArgumentsMap.
+    if (OnlyValidUsers)
+      FunctionPointerArgumentsMap[F] = std::move(AbstractArguments);
+  }
+}
+
+template <typename AARGetterT, typename DomTreeGetterTy>
+static bool deriveCalleeArgumentAttrs(ArrayRef<Function *> SCCNodes,
+                                      AARGetterT &AARGetter,
+                                      DomTreeGetterTy &DomTreeGetter) {
+  DenseMap<Function *, SmallVector<CallSite, 4>> FunctionCallSitesMap;
+  DenseMap<Function *, SmallVector<AbstractArgument, 4>>
+      FunctionPointerArgumentsMap;
+
+  // First collect all call sites (direct and callback calls) for the functions
+  // in the SCC.
+  collectAllCallSites(SCCNodes, FunctionCallSitesMap,
+                      FunctionPointerArgumentsMap);
+
+  // If there was no internal function with pointer arguments and valid, thus
+  // statically known, call sites, we are done.
+  if (FunctionCallSitesMap.empty())
+    return false;
+
+  // Bookkeeping.
+  NumFunctionsWithStaticCallSites += FunctionCallSitesMap.size();
+  NumSCCsWithStaticCallSites++;
+
+  // We are also done if no argument has an abstract state with optimistically
+  // assumed attributes. To determine this, and to later speed up the fixpoint
+  // computation, we remove all mappings for functions without annotateable
+  // arguments.
+  for (auto &It : FunctionPointerArgumentsMap) {
+    unsigned NumArgsWithAttrs = 0;
+    for (AbstractArgument &AA : It.second)
+      NumArgsWithAttrs += AA.Attrs.hasAny();
+    if (!NumArgsWithAttrs)
+      FunctionPointerArgumentsMap.erase(It.getFirst());
+  }
+
+  // Check again if we are now done.
+  if (FunctionCallSitesMap.empty())
+    return false;
+
+  const DataLayout &DL = SCCNodes.front()->getParent()->getDataLayout();
+
+  // TODO: MaxIterations is an arbitrary chosen threshold that should be
+  //       revisited. It is also unclear if we even need it (in practise).
+  int MaxIterations = 6;
+
+  // Since we have at least one function that could potentially be annotated, we
+  // perform a fixpoint iteration to determine which attributes we can actually
+  // manifest.
+  bool Fixpoint;
+  do {
+    Fixpoint = true;
+
+    // We analyze one function at a time and iterate over all call sites
+    // _inside_ that function. This way we can use the analysis information
+    // for the function multiple times.
+    for (auto &It : FunctionCallSitesMap) {
+      Function &CallSiteFunction = *It.first;
+      auto &CallSites = It.second;
+
+      AAResults &AAR = AARGetter(CallSiteFunction);
+      const DominatorTree &DT = DomTreeGetter(CallSiteFunction);
+
+      // For each abstract call site in the function (CallSiteFunction) we first
+      // lookup the abstract argument states for the pointer arguments of the
+      // called function.
+      for (CallSite &CS : CallSites) {
+
+        // Check if the callee is still mapped to abstract arguments. They could
+        // have been removed if none of them had attributes left that we
+        // potentially could add to them.
+        const auto &FPAMIt =
+            FunctionPointerArgumentsMap.find(CS.getCalledFunction());
+        if (FPAMIt == FunctionPointerArgumentsMap.end())
+          continue;
+
+        // Since we have abstract arguments for the callee, we will now check if
+        // their attributes are still valid and remove the ones that are not.
+        auto &AbstractArguments = FPAMIt->getSecond();
+        assert(!AbstractArguments.empty() &&
+               "Abstract arguments were mapped but empty");
+
+        unsigned NumArguments = AbstractArguments.size();
+        unsigned NumArgsWithAttrs = 0;
+        for (unsigned u = 0; u < NumArguments; u++) {
+          // If no attribute is set, there is nothing to remove.
+          if (!AbstractArguments[u].Attrs.hasAny())
+            continue;
+
+          // If attributes are set, we remove invalid ones. In case this changes
+          // the attributes, thus some were removed, we have not found a
+          // fixpoint yet.
+          Value *Param = CS.getArgOperand(u)->stripPointerCasts();
+          Fixpoint &=
+              !removeInvalidAttributes(Param, AbstractArguments[u], CS, DL, AAR,
+                                       DT, FunctionPointerArgumentsMap);
+
+          // If there are no attributes set in the new state, we might be able
+          // to remove the called function (CS.Callee) from the subsequent
+          // fixpoint iterations. Thus, we check if any argument is still set.
+          if (AbstractArguments[u].Attrs.hasAny())
+            NumArgsWithAttrs++;
+        }
+
+        // If no argument of the callee has attributes left, we eliminate the
+        // callee from subsequent iterations.
+        if (!NumArgsWithAttrs)
+          FunctionPointerArgumentsMap.erase(CS.getCalledFunction());
+      }
+    }
+  } while (!Fixpoint && --MaxIterations > 0);
+
+  // Check if a fixpoint was reached or the maximal number of iterations. In
+  // case of the latter, bail as we do not have a sound solution at this point.
+  if (!Fixpoint)
+    return false;
+
+  // We also bail if no functions with annotatable arguments remain.
+  if (FunctionCallSitesMap.empty())
+    return false;
+
+  LLVMContext &Ctx = SCCNodes.front()->getContext();
+
+  // For the ones that are still left, we iterate over the pointer arguments,
+  // check the attributes that are set, and manifest them in the IR.
+  for (auto &It : FunctionPointerArgumentsMap) {
+    for (AbstractArgument &AA : It.second) {
+
+      if (!AA.Attrs.hasAny())
+        continue;
+
+      // We avoid adding a dereferenceableOrNull annotation if it is implied
+      // by a new dereferenceable attribute.
+      if (AA.Attrs.getDereferenceableAttr() >=
+          AA.Attrs.getDereferenceableOrNullAttr())
+        AA.Attrs.clearDereferenceableOrNullAttr();
+
+      // Combine dereferenceableOrNull and nonNull to dereferenceable.
+      if (AA.Attrs.hasNonNullAttr() &&
+          AA.Attrs.hasDereferenceableOrNullAttr()) {
+        AA.Attrs.setDereferenceableAttr(
+            std::max(AA.Attrs.getDereferenceableAttr(),
+                     AA.Attrs.getDereferenceableOrNullAttr()));
+        AA.Attrs.clearDereferenceableOrNullAttr();
+      }
+
+      // Clear nonnull if dereferenceable is present.
+      if (AA.Attrs.hasDereferenceableAttr())
+        AA.Attrs.clearNonNullAttr();
+
+      // We avoid alignment annotations that are implied by the data layout.
+      if (AA.Attrs.hasAlignmentAttr() &&
+          AA.Arg->getPointerAlignment(DL) >= AA.Attrs.getAlignmentAttr())
+        AA.Attrs.clearAlignmentAttr();
+
+      // Since read-none implies read-only and write-only we do only manifest
+      // the first.
+      if (AA.Attrs.hasReadNoneAttr()) {
+        AA.Attrs.clearReadOnlyAttr();
+        AA.Attrs.clearWriteOnlyAttr();
+      }
+
+      // Helper to manifest attributes for the argument (AA.Arg). All attributes
+      // that are set in the abstract state (AA.Attrs) are materialized here.
+#define ABSTRACT_ARGUMENT_ATTR_FUNC(NAME, KIND, INIT)                          \
+  if (AA.Attrs.has##NAME##Attr()) {                                            \
+    if (std::is_same<decltype(INIT), bool>::value)                             \
+      AA.Arg->addAttr(KIND);                                                   \
+    else                                                                       \
+      AA.Arg->addAttr(Attribute::get(Ctx, KIND, AA.Attrs.get##NAME##Attr()));  \
+    Num##NAME##Arg++;                                                          \
+  }
+
+      ABSTRACT_ARGUMENT_ATTRIBUTES()
+#undef ABSTRACT_ARGUMENT_ATTR_FUNC
+    }
+  }
+
+  return true;
+}
+
+#undef ABSTRACT_ARGUMENT_ATTRIBUTES
+
 /// Deduce returned attributes for the SCC.
 static bool addArgumentReturnedAttrs(const SCCNodeSet &SCCNodes) {
   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 (Function *F : SCCNodes) {
     // 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;
+          ++NumNoCaptureArg;
           Changed = true;
         }
       }
       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;
+            ++NumNoCaptureArg;
             Changed = true;
           } 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 (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;
+        ++NumNoCaptureArg;
         Changed = true;
       }
       continue;
     }
 
     bool SCCCaptured = false;
     for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
          I != E && !SCCCaptured; ++I) {
for (auto I = ArgumentSCC.begin(), E = ArgumentSCC.end();
       }
     }
     if (SCCCaptured)
       continue;
 
     for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) {
       Argument *A = ArgumentSCC[i]->Definition;
       A->addAttr(Attribute::NoCapture);
-      ++NumNoCapture;
+      ++NumNoCaptureArg;
       Changed = true;
     }
 
     // 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.
     //
ReversePostOrderFunctionAttrsLegacyPass() : ModulePass(ID) {
     initializeReversePostOrderFunctionAttrsLegacyPassPass(
         *PassRegistry::getPassRegistry());
   }
 
   bool runOnModule(Module &M) override;
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
+    getAAResultsAnalysisUsage(AU);
+    AU.addRequired<AssumptionCacheTracker>();
+    AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<CallGraphWrapperPass>();
     AU.addPreserved<CallGraphWrapperPass>();
   }
 };
 
 } // end anonymous namespace
 
 char ReversePostOrderFunctionAttrsLegacyPass::ID = 0;
if (!I)
       return false;
     CallSite CS(I);
     if (!CS || !CS.getParent()->getParent()->doesNotRecurse())
       return false;
   }
   return setDoesNotRecurse(F);
 }
 
-static bool deduceFunctionAttributeInRPO(Module &M, CallGraph &CG) {
+template <typename AARGetterT, typename DomTreeGetterTy>
+static bool deduceFunctionAttributeInRPO(Module &M, CallGraph &CG,
+                                         AARGetterT &&AARGetter,
+                                         DomTreeGetterTy &DomTreeGetter) {
   // 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;
+  //
+  // NOTE: The above reasoning is only true for the identification of
+  //       non-recursive singleton SCCs. However, we also want to derive callee
+  //       attributes in reverse post order. For this the SCCs do not need to be
+  //       singletons nor is the "egregious cheat" still applicable.
+  // FIXME: Perform a real reverse post order traversal over the SCCs.
+  SmallVector<SmallVector<Function *, 4>, 16> Worklist;
   for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
-    if (I->size() != 1)
+    assert(I->size() > 0);
+    // If we do not propagate attributes to the callee we are only interested
+    // in singleton SCCs.
+    if (DisableCalleeArgumentAttrInference && I->size() > 1)
+      continue;
+
+    // Skip singleton SCCs that do not have a definition.
+    if (I->size() == 1 && (!I->front()->getFunction() ||
+                           I->front()->getFunction()->isDeclaration()))
       continue;
 
-    Function *F = I->front()->getFunction();
-    if (F && !F->isDeclaration() && !F->doesNotRecurse() &&
-        F->hasInternalLinkage())
-      Worklist.push_back(F);
+    SmallVector<Function *, 4> SCCNodes;
+    for (auto It : *I) {
+      Function *F = It->getFunction();
+      assert(F && !F->isDeclaration() &&
+             "Non singleton CGSCC should have a function definition.");
+      SCCNodes.push_back(F);
+    }
+
+    Worklist.push_back(std::move(SCCNodes));
   }
 
   bool Changed = false;
-  for (auto *F : llvm::reverse(Worklist))
-    Changed |= addNoRecurseAttrsTopDown(*F);
+  for (auto &SCCNodes : llvm::reverse(Worklist)) {
+    if (SCCNodes.size() == 1 && !SCCNodes.front()->doesNotRecurse() &&
+        SCCNodes.front()->hasInternalLinkage())
+      Changed |= addNoRecurseAttrsTopDown(*SCCNodes.front());
+    if (!DisableCalleeArgumentAttrInference)
+      Changed |= deriveCalleeArgumentAttrs(SCCNodes, AARGetter, DomTreeGetter);
+  }
 
   return Changed;
 }
 
 bool ReversePostOrderFunctionAttrsLegacyPass::runOnModule(Module &M) {
   if (skipModule(M))
     return false;
 
   auto &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
 
-  return deduceFunctionAttributeInRPO(M, CG);
+  auto DomTreeGetter = [&](Function &F) -> const DominatorTree & {
+    return getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
+  };
+
+  return deduceFunctionAttributeInRPO(M, CG, LegacyAARGetter(*this),
+                                      DomTreeGetter);
 }
 
 PreservedAnalyses
 ReversePostOrderFunctionAttrsPass::run(Module &M, ModuleAnalysisManager &AM) {
   auto &CG = AM.getResult<CallGraphAnalysis>(M);
 
-  if (!deduceFunctionAttributeInRPO(M, CG))
+  FunctionAnalysisManager &FAM =
+      AM.getResult<FunctionAnalysisManagerModuleProxy>(M).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);
+  };
+  auto DomTreeGetter = [&](Function &F) -> const DominatorTree & {
+    return FAM.getResult<DominatorTreeAnalysis>(F);
+  };
+
+  if (!deduceFunctionAttributeInRPO(M, CG, AARGetter, DomTreeGetter))
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
   PA.preserve<CallGraphAnalysis>();
   return PA;
 }

test/Other/opt-O2-pipeline.ll

 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Combine redundant instructions
 ; CHECK-NEXT:     A No-Op Barrier Pass
 ; CHECK-NEXT:     Eliminate Available Externally Globals
 ; CHECK-NEXT:     CallGraph Construction
 ; CHECK-NEXT:     Deduce function attributes in RPO
+; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
 ; CHECK-NEXT:     Global Variable Optimizer
 ; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
 ; CHECK-NEXT:     Dead Global Elimination
 ; CHECK-NEXT:     CallGraph Construction
 ; CHECK-NEXT:     Globals Alias Analysis
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Float to int
 ; CHECK-NEXT:       Dominator Tree Construction

 ; CHECK-NEXT: Pass Arguments:
 ; CHECK-NEXT: Target Library Information
 ; CHECK-NEXT:   FunctionPass Manager
 ; CHECK-NEXT:     Dominator Tree Construction
 ; CHECK-NEXT:     Natural Loop Information
 ; CHECK-NEXT:     Branch Probability Analysis
 ; CHECK-NEXT:     Block Frequency Analysis
 ; CHECK-NEXT: Pass Arguments:
+; CHECK-NEXT:   FunctionPass Manager
+; CHECK-NEXT:     Dominator Tree Constructio
+; CHECK-NEXT: Pass Arguments:
 ; CHECK-NEXT: Target Library Information
 ; CHECK-NEXT:   FunctionPass Manager
 ; CHECK-NEXT:     Dominator Tree Construction
 ; CHECK-NEXT:     Natural Loop Information
 ; CHECK-NEXT:     Branch Probability Analysis
 ; CHECK-NEXT:     Block Frequency Analysis
 
 define void @f() {
   ret void
 }

test/Other/opt-O3-pipeline.ll

 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Combine redundant instructions
 ; CHECK-NEXT:     A No-Op Barrier Pass
 ; CHECK-NEXT:     Eliminate Available Externally Globals
 ; CHECK-NEXT:     CallGraph Construction
 ; CHECK-NEXT:     Deduce function attributes in RPO
+; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
 ; CHECK-NEXT:     Global Variable Optimizer
 ; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
 ; CHECK-NEXT:     Dead Global Elimination
 ; CHECK-NEXT:     CallGraph Construction
 ; CHECK-NEXT:     Globals Alias Analysis
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Float to int
 ; CHECK-NEXT:       Dominator Tree Construction

 ; CHECK-NEXT: Pass Arguments:
 ; CHECK-NEXT: Target Library Information
 ; CHECK-NEXT:   FunctionPass Manager
 ; CHECK-NEXT:     Dominator Tree Construction
 ; CHECK-NEXT:     Natural Loop Information
 ; CHECK-NEXT:     Branch Probability Analysis
 ; CHECK-NEXT:     Block Frequency Analysis
 ; CHECK-NEXT: Pass Arguments:
+; CHECK-NEXT:   FunctionPass Manager
+; CHECK-NEXT:     Dominator Tree Constructio
+; CHECK-NEXT: Pass Arguments:
 ; CHECK-NEXT: Target Library Information
 ; CHECK-NEXT:   FunctionPass Manager
 ; CHECK-NEXT:     Dominator Tree Construction
 ; CHECK-NEXT:     Natural Loop Information
 ; CHECK-NEXT:     Branch Probability Analysis
 ; CHECK-NEXT:     Block Frequency Analysis
 
 define void @f() {
   ret void
 }

test/Other/opt-Os-pipeline.ll

 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Combine redundant instructions
 ; CHECK-NEXT:     A No-Op Barrier Pass
 ; CHECK-NEXT:     Eliminate Available Externally Globals
 ; CHECK-NEXT:     CallGraph Construction
 ; CHECK-NEXT:     Deduce function attributes in RPO
+; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
 ; CHECK-NEXT:     Global Variable Optimizer
 ; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
 ; CHECK-NEXT:     Dead Global Elimination
 ; CHECK-NEXT:     CallGraph Construction
 ; CHECK-NEXT:     Globals Alias Analysis
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Float to int
 ; CHECK-NEXT:       Dominator Tree Construction

 ; CHECK-NEXT: Pass Arguments:
 ; CHECK-NEXT: Target Library Information
 ; CHECK-NEXT:   FunctionPass Manager
 ; CHECK-NEXT:     Dominator Tree Construction
 ; CHECK-NEXT:     Natural Loop Information
 ; CHECK-NEXT:     Branch Probability Analysis
 ; CHECK-NEXT:     Block Frequency Analysis
 ; CHECK-NEXT: Pass Arguments:
+; CHECK-NEXT:   FunctionPass Manager
+; CHECK-NEXT:     Dominator Tree Constructio
+; CHECK-NEXT: Pass Arguments:
 ; CHECK-NEXT: Target Library Information
 ; CHECK-NEXT:   FunctionPass Manager
 ; CHECK-NEXT:     Dominator Tree Construction
 ; CHECK-NEXT:     Natural Loop Information
 ; CHECK-NEXT:     Branch Probability Analysis
 ; CHECK-NEXT:     Block Frequency Analysis
 
 define void @f() {
   ret void
 }

test/Other/pass-pipelines.ll

 ; CHECK-O2: A No-Op Barrier Pass
 ; CHECK-O2-NEXT: Eliminate Available Externally
 ; Inferring function attribute should be right after the CGSCC pipeline, before
 ; any other optimizations/analyses.
 ; CHECK-O2-NEXT: CallGraph
 ; CHECK-O2-NEXT: Deduce function attributes in RPO
 ; CHECK-O2-NOT: Manager
 ; Reduce the size of the IR ASAP after the inliner.
+; CHECK-O2-NEXT: Unnamed pass: implement Pass::getPassName()
 ; CHECK-O2-NEXT: Global Variable Optimizer
 ; CHECK-O2: Dead Global Elimination
 ; Next is the late function pass pipeline.
 ; CHECK-O2: FunctionPass Manager
 ; CHECK-O2-NOT: Manager
 ; We rotate loops prior to vectorization.
 ; CHECK-O2: Loop Pass Manager
 ; CHECK-O2-NEXT: Rotate Loops

test/Transforms/FunctionAttrs/internal_alias.ll

+; RUN: opt -S -functionattrs -rpo-functionattrs < %s | FileCheck %s
+; RUN: opt -S -functionattrs -rpo-functionattrs -enable-nonnull-arg-prop < %s | FileCheck %s --check-prefix=NONNULL
+;
+; Verify we do not mark the arguments of the alias function as noalias.
+; This could happend because the function only accesses argument pointers
+; and the passed values are not aliasing directly at the call site. However,
+; pointers derived from them actually do.
+;
+; static int alias(int *A, int *B) {
+;   return A[1] + B[0];
+; }
+; 
+; int g(int *A) {
+;   return alias(A, A+1);
+; }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define i32 @g(i32* %A) #0 {
+entry:
+  %add.ptr = getelementptr inbounds i32, i32* %A, i64 1
+  %call = call i32 @alias(i32* %A, i32* nonnull %add.ptr)
+  ret i32 %call
+}
+
+; CHECK: define internal i32 @alias(i32* nocapture readonly %A, i32* nocapture readonly %B)
+; NONNULL: define internal i32 @alias(i32* nocapture readonly %A, i32* nocapture nonnull readonly %B)
+define internal i32 @alias(i32* %A, i32* %B) #0 {
+entry:
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 1
+  %0 = load i32, i32* %arrayidx, align 4
+  %1 = load i32, i32* %B, align 4
+  %add = add nsw i32 %0, %1
+  ret i32 %add
+}
+
+attributes #0 = { nounwind argmemonly }

test/Transforms/FunctionAttrs/internal_callee.ll

+; RUN: opt -S -rpo-functionattrs < %s | FileCheck %s
+; RUN: opt -S -functionattrs -rpo-functionattrs -enable-nonnull-arg-prop < %s | FileCheck %s --check-prefix=PORPO
+;
+; 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 dereferenceable_or_null(4) %A)
+; PORPO: define internal void @rec_internal(i32* noalias nocapture dereferenceable(4) %A)
+;
+; Function Attrs: noinline nounwind uwtable
+define internal void @rec_internal(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_internal(i32* %A)
+  br label %if.end
+
+if.end:                                           ; preds = %entry, %if.then
+  ret void
+}
+
+attributes #0 = { noinline nounwind uwtable }

test/Transforms/FunctionAttrs/internal_large-agg.ll

+; RUN: opt -S -functionattrs -rpo-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 readonly align 32 dereferenceable(261120) %x, %struct.x* noalias align 4 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 -rpo-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.
+;
+; 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"
+
+; CHECK: define i32 @bar()
+
+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 dereferenceable_or_null(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 -rpo-functionattrs < %s | FileCheck %s
+; RUN: opt -S -functionattrs -rpo-functionattrs -enable-nonnull-arg-prop < %s | FileCheck %s --check-prefix=PORPO
+;
+; Check that we derive noalias attributes for the arguments of the
+; noalias_args_argmem function from its call sites. For the noalias_args
+; function we shall only do so for the second argument.
+;
+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* %A, i32* noalias %B)
+; PORPO: define internal i32 @noalias_args(i32* nocapture readonly %A, i32* noalias nocapture readonly %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 %A, i32* noalias %B)
+; PORPO: define internal i32 @noalias_args_argmem(i32* noalias nocapture readonly %A, i32* noalias nocapture readonly %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 }