AttributorAttributes.cpp

Go to the documentation of this file.

//===- AttributorAttributes.cpp - Attributes for Attributor deduction -----===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// See the Attributor.h file comment and the class descriptions in that file for
// more information.
//
//===----------------------------------------------------------------------===//
 
#include "llvm/Transforms/IPO/Attributor.h"
 
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetOperations.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumeBundleQueries.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/CaptureTracking.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LazyValueInfo.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/Assumptions.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/GlobalValue.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/NoFolder.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Support/Alignment.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/GraphWriter.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/IPO/ArgumentPromotion.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <cassert>
 
using namespace llvm;
 
#define DEBUG_TYPE "attributor"
 
static cl::opt<bool> ManifestInternal(
    "attributor-manifest-internal", cl::Hidden,
    cl::desc("Manifest Attributor internal string attributes."),
    cl::init(false));
 
static cl::opt<int> MaxHeapToStackSize("max-heap-to-stack-size", cl::init(128),
                                       cl::Hidden);
 
template <>
unsigned llvm::PotentialConstantIntValuesState::MaxPotentialValues = 0;
 
static cl::opt<unsigned, true> MaxPotentialValues(
    "attributor-max-potential-values", cl::Hidden,
    cl::desc("Maximum number of potential values to be "
             "tracked for each position."),
    cl::location(llvm::PotentialConstantIntValuesState::MaxPotentialValues),
    cl::init(7));
 
static cl::opt<unsigned> MaxInterferingAccesses(
    "attributor-max-interfering-accesses", cl::Hidden,
    cl::desc("Maximum number of interfering accesses to "
             "check before assuming all might interfere."),
    cl::init(6));
 
STATISTIC(NumAAs, "Number of abstract attributes created");
 
// Some helper macros to deal with statistics tracking.
//
// Usage:
// For simple IR attribute tracking overload trackStatistics in the abstract
// attribute and choose the right STATS_DECLTRACK_********* macro,
// e.g.,:
//  void trackStatistics() const override {
//    STATS_DECLTRACK_ARG_ATTR(returned)
//  }
// If there is a single "increment" side one can use the macro
// STATS_DECLTRACK with a custom message. If there are multiple increment
// sides, STATS_DECL and STATS_TRACK can also be used separately.
//
#define BUILD_STAT_MSG_IR_ATTR(TYPE, NAME)                                     \
  ("Number of " #TYPE " marked '" #NAME "'")
#define BUILD_STAT_NAME(NAME, TYPE) NumIR##TYPE##_##NAME
#define STATS_DECL_(NAME, MSG) STATISTIC(NAME, MSG);
#define STATS_DECL(NAME, TYPE, MSG)                                            \
  STATS_DECL_(BUILD_STAT_NAME(NAME, TYPE), MSG);
#define STATS_TRACK(NAME, TYPE) ++(BUILD_STAT_NAME(NAME, TYPE));
#define STATS_DECLTRACK(NAME, TYPE, MSG)                                       \
  {                                                                            \
    STATS_DECL(NAME, TYPE, MSG)                                                \
    STATS_TRACK(NAME, TYPE)                                                    \
  }
#define STATS_DECLTRACK_ARG_ATTR(NAME)                                         \
  STATS_DECLTRACK(NAME, Arguments, BUILD_STAT_MSG_IR_ATTR(arguments, NAME))
#define STATS_DECLTRACK_CSARG_ATTR(NAME)                                       \
  STATS_DECLTRACK(NAME, CSArguments,                                           \
                  BUILD_STAT_MSG_IR_ATTR(call site arguments, NAME))
#define STATS_DECLTRACK_FN_ATTR(NAME)                                          \
  STATS_DECLTRACK(NAME, Function, BUILD_STAT_MSG_IR_ATTR(functions, NAME))
#define STATS_DECLTRACK_CS_ATTR(NAME)                                          \
  STATS_DECLTRACK(NAME, CS, BUILD_STAT_MSG_IR_ATTR(call site, NAME))
#define STATS_DECLTRACK_FNRET_ATTR(NAME)                                       \
  STATS_DECLTRACK(NAME, FunctionReturn,                                        \
                  BUILD_STAT_MSG_IR_ATTR(function returns, NAME))
#define STATS_DECLTRACK_CSRET_ATTR(NAME)                                       \
  STATS_DECLTRACK(NAME, CSReturn,                                              \
                  BUILD_STAT_MSG_IR_ATTR(call site returns, NAME))
#define STATS_DECLTRACK_FLOATING_ATTR(NAME)                                    \
  STATS_DECLTRACK(NAME, Floating,                                              \
                  ("Number of floating values known to be '" #NAME "'"))
 
// Specialization of the operator<< for abstract attributes subclasses. This
// disambiguates situations where multiple operators are applicable.
namespace llvm {
#define PIPE_OPERATOR(CLASS)                                                   \
  raw_ostream &operator<<(raw_ostream &OS, const CLASS &AA) {                  \
    return OS << static_cast<const AbstractAttribute &>(AA);                   \
  }
 
PIPE_OPERATOR(AAIsDead)
PIPE_OPERATOR(AANoUnwind)
PIPE_OPERATOR(AANoSync)
PIPE_OPERATOR(AANoRecurse)
PIPE_OPERATOR(AAWillReturn)
PIPE_OPERATOR(AANoReturn)
PIPE_OPERATOR(AAReturnedValues)
PIPE_OPERATOR(AANonNull)
PIPE_OPERATOR(AANoAlias)
PIPE_OPERATOR(AADereferenceable)
PIPE_OPERATOR(AAAlign)
PIPE_OPERATOR(AAInstanceInfo)
PIPE_OPERATOR(AANoCapture)
PIPE_OPERATOR(AAValueSimplify)
PIPE_OPERATOR(AANoFree)
PIPE_OPERATOR(AAHeapToStack)
PIPE_OPERATOR(AAReachability)
PIPE_OPERATOR(AAMemoryBehavior)
PIPE_OPERATOR(AAMemoryLocation)
PIPE_OPERATOR(AAValueConstantRange)
PIPE_OPERATOR(AAPrivatizablePtr)
PIPE_OPERATOR(AAUndefinedBehavior)
PIPE_OPERATOR(AAPotentialConstantValues)
PIPE_OPERATOR(AANoUndef)
PIPE_OPERATOR(AACallEdges)
PIPE_OPERATOR(AAFunctionReachability)
PIPE_OPERATOR(AAPointerInfo)
PIPE_OPERATOR(AAAssumptionInfo)
 
#undef PIPE_OPERATOR
 
template <>
ChangeStatus clampStateAndIndicateChange<DerefState>(DerefState &S,
                                                     const DerefState &R) {
  ChangeStatus CS0 =
      clampStateAndIndicateChange(S.DerefBytesState, R.DerefBytesState);
  ChangeStatus CS1 = clampStateAndIndicateChange(S.GlobalState, R.GlobalState);
  return CS0 | CS1;
}
 
} // namespace llvm
 
/// Get pointer operand of memory accessing instruction. If \p I is
/// not a memory accessing instruction, return nullptr. If \p AllowVolatile,
/// is set to false and the instruction is volatile, return nullptr.
static const Value *getPointerOperand(const Instruction *I,
                                      bool AllowVolatile) {
  if (!AllowVolatile && I->isVolatile())
    return nullptr;
 
  if (auto *LI = dyn_cast<LoadInst>(I)) {
    return LI->getPointerOperand();
  }
 
  if (auto *SI = dyn_cast<StoreInst>(I)) {
    return SI->getPointerOperand();
  }
 
  if (auto *CXI = dyn_cast<AtomicCmpXchgInst>(I)) {
    return CXI->getPointerOperand();
  }
 
  if (auto *RMWI = dyn_cast<AtomicRMWInst>(I)) {
    return RMWI->getPointerOperand();
  }
 
  return nullptr;
}
 
/// Helper function to create a pointer of type \p ResTy, based on \p Ptr, and
/// advanced by \p Offset bytes. To aid later analysis the method tries to build
/// getelement pointer instructions that traverse the natural type of \p Ptr if
/// possible. If that fails, the remaining offset is adjusted byte-wise, hence
/// through a cast to i8*.
///
/// TODO: This could probably live somewhere more prominantly if it doesn't
///       already exist.
static Value *constructPointer(Type *ResTy, Type *PtrElemTy, Value *Ptr,
                               int64_t Offset, IRBuilder<NoFolder> &IRB,
                               const DataLayout &DL) {
  assert(Offset >= 0 && "Negative offset not supported yet!");
  LLVM_DEBUG(dbgs() << "Construct pointer: " << *Ptr << " + " << Offset
                    << "-bytes as " << *ResTy << "\n");
 
  if (Offset) {
    Type *Ty = PtrElemTy;
    APInt IntOffset(DL.getIndexTypeSizeInBits(Ptr->getType()), Offset);
    SmallVector<APInt> IntIndices = DL.getGEPIndicesForOffset(Ty, IntOffset);
 
    SmallVector<Value *, 4> ValIndices;
    std::string GEPName = Ptr->getName().str();
    for (const APInt &Index : IntIndices) {
      ValIndices.push_back(IRB.getInt(Index));
      GEPName += "." + std::to_string(Index.getZExtValue());
    }
 
    // Create a GEP for the indices collected above.
    Ptr = IRB.CreateGEP(PtrElemTy, Ptr, ValIndices, GEPName);
 
    // If an offset is left we use byte-wise adjustment.
    if (IntOffset != 0) {
      Ptr = IRB.CreateBitCast(Ptr, IRB.getInt8PtrTy());
      Ptr = IRB.CreateGEP(IRB.getInt8Ty(), Ptr, IRB.getInt(IntOffset),
                          GEPName + ".b" + Twine(IntOffset.getZExtValue()));
    }
  }
 
  // Ensure the result has the requested type.
  Ptr = IRB.CreatePointerBitCastOrAddrSpaceCast(Ptr, ResTy,
                                                Ptr->getName() + ".cast");
 
  LLVM_DEBUG(dbgs() << "Constructed pointer: " << *Ptr << "\n");
  return Ptr;
}
 
/// Recursively visit all values that might become \p IRP at some point. This
/// will be done by looking through cast instructions, selects, phis, and calls
/// with the "returned" attribute. Once we cannot look through the value any
/// further, the callback \p VisitValueCB is invoked and passed the current
/// value, the \p State, and a flag to indicate if we stripped anything.
/// Stripped means that we unpacked the value associated with \p IRP at least
/// once. Note that the value used for the callback may still be the value
/// associated with \p IRP (due to PHIs). To limit how much effort is invested,
/// we will never visit more values than specified by \p MaxValues.
/// If \p VS does not contain the Interprocedural bit, only values valid in the
/// scope of \p CtxI will be visited and simplification into other scopes is
/// prevented.
template <typename StateTy>
static bool genericValueTraversal(
    Attributor &A, IRPosition IRP, const AbstractAttribute &QueryingAA,
    StateTy &State,
    function_ref<bool(Value &, const Instruction *, StateTy &, bool)>
        VisitValueCB,
    const Instruction *CtxI, bool &UsedAssumedInformation,
    bool UseValueSimplify = true, int MaxValues = 16,
    function_ref<Value *(Value *)> StripCB = nullptr,
    AA::ValueScope VS = AA::Interprocedural) {
 
  struct LivenessInfo {
    const AAIsDead *LivenessAA = nullptr;
    bool AnyDead = false;
  };
  SmallMapVector<const Function *, LivenessInfo, 4> LivenessAAs;
  auto GetLivenessInfo = [&](const Function &F) -> LivenessInfo & {
    LivenessInfo &LI = LivenessAAs[&F];
    if (!LI.LivenessAA)
      LI.LivenessAA = &A.getAAFor<AAIsDead>(QueryingAA, IRPosition::function(F),
                                            DepClassTy::NONE);
    return LI;
  };
 
  Value *InitialV = &IRP.getAssociatedValue();
  using Item = std::pair<Value *, const Instruction *>;
  SmallSet<Item, 16> Visited;
  SmallVector<Item, 16> Worklist;
  Worklist.push_back({InitialV, CtxI});
 
  int Iteration = 0;
  do {
    Item I = Worklist.pop_back_val();
    Value *V = I.first;
    CtxI = I.second;
    if (StripCB)
      V = StripCB(V);
 
    // Check if we should process the current value. To prevent endless
    // recursion keep a record of the values we followed!
    if (!Visited.insert(I).second)
      continue;
 
    // Make sure we limit the compile time for complex expressions.
    if (Iteration++ >= MaxValues) {
      LLVM_DEBUG(dbgs() << "Generic value traversal reached iteration limit: "
                        << Iteration << "!\n");
      return false;
    }
 
    // Explicitly look through calls with a "returned" attribute if we do
    // not have a pointer as stripPointerCasts only works on them.
    Value *NewV = nullptr;
    if (V->getType()->isPointerTy()) {
      NewV = V->stripPointerCasts();
    } else {
      auto *CB = dyn_cast<CallBase>(V);
      if (CB && CB->getCalledFunction()) {
        for (Argument &Arg : CB->getCalledFunction()->args())
          if (Arg.hasReturnedAttr()) {
            NewV = CB->getArgOperand(Arg.getArgNo());
            break;
          }
      }
    }
    if (NewV && NewV != V) {
      Worklist.push_back({NewV, CtxI});
      continue;
    }
 
    // Look through select instructions, visit assumed potential values.
    if (auto *SI = dyn_cast<SelectInst>(V)) {
      Optional<Constant *> C = A.getAssumedConstant(
          *SI->getCondition(), QueryingAA, UsedAssumedInformation);
      bool NoValueYet = !C.hasValue();
      if (NoValueYet || isa_and_nonnull<UndefValue>(*C))
        continue;
      if (auto *CI = dyn_cast_or_null<ConstantInt>(*C)) {
        if (CI->isZero())
          Worklist.push_back({SI->getFalseValue(), CtxI});
        else
          Worklist.push_back({SI->getTrueValue(), CtxI});
        continue;
      }
      // We could not simplify the condition, assume both values.(
      Worklist.push_back({SI->getTrueValue(), CtxI});
      Worklist.push_back({SI->getFalseValue(), CtxI});
      continue;
    }
 
    // Look through phi nodes, visit all live operands.
    if (auto *PHI = dyn_cast<PHINode>(V)) {
      LivenessInfo &LI = GetLivenessInfo(*PHI->getFunction());
      for (unsigned u = 0, e = PHI->getNumIncomingValues(); u < e; u++) {
        BasicBlock *IncomingBB = PHI->getIncomingBlock(u);
        if (LI.LivenessAA->isEdgeDead(IncomingBB, PHI->getParent())) {
          LI.AnyDead = true;
          UsedAssumedInformation |= !LI.LivenessAA->isAtFixpoint();
          continue;
        }
        Worklist.push_back(
            {PHI->getIncomingValue(u), IncomingBB->getTerminator()});
      }
      continue;
    }
 
    if (auto *Arg = dyn_cast<Argument>(V)) {
      if ((VS & AA::Interprocedural) && !Arg->hasPassPointeeByValueCopyAttr()) {
        SmallVector<Item> CallSiteValues;
        bool UsedAssumedInformation = false;
        if (A.checkForAllCallSites(
                [&](AbstractCallSite ACS) {
                  // Callbacks might not have a corresponding call site operand,
                  // stick with the argument in that case.
                  Value *CSOp = ACS.getCallArgOperand(*Arg);
                  if (!CSOp)
                    return false;
                  CallSiteValues.push_back({CSOp, ACS.getInstruction()});
                  return true;
                },
                *Arg->getParent(), true, &QueryingAA, UsedAssumedInformation)) {
          Worklist.append(CallSiteValues);
          continue;
        }
      }
    }
 
    if (UseValueSimplify && !isa<Constant>(V)) {
      Optional<Value *> SimpleV =
          A.getAssumedSimplified(*V, QueryingAA, UsedAssumedInformation);
      if (!SimpleV.hasValue())
        continue;
      Value *NewV = SimpleV.getValue();
      if (NewV && NewV != V) {
        if ((VS & AA::Interprocedural) || !CtxI ||
            AA::isValidInScope(*NewV, CtxI->getFunction())) {
          Worklist.push_back({NewV, CtxI});
          continue;
        }
      }
    }
 
    if (auto *LI = dyn_cast<LoadInst>(V)) {
      bool UsedAssumedInformation = false;
      // If we ask for the potentially loaded values from the initial pointer we
      // will simply end up here again. The load is as far as we can make it.
      if (LI->getPointerOperand() != InitialV) {
        SmallSetVector<Value *, 4> PotentialCopies;
        SmallSetVector<Instruction *, 4> PotentialValueOrigins;
        if (AA::getPotentiallyLoadedValues(A, *LI, PotentialCopies,
                                           PotentialValueOrigins, QueryingAA,
                                           UsedAssumedInformation,
                                           /* OnlyExact */ true)) {
          // Values have to be dynamically unique or we loose the fact that a
          // single llvm::Value might represent two runtime values (e.g., stack
          // locations in different recursive calls).
          bool DynamicallyUnique =
              llvm::all_of(PotentialCopies, [&A, &QueryingAA](Value *PC) {
                return AA::isDynamicallyUnique(A, QueryingAA, *PC);
              });
          if (DynamicallyUnique &&
              ((VS & AA::Interprocedural) || !CtxI ||
               llvm::all_of(PotentialCopies, [CtxI](Value *PC) {
                 return AA::isValidInScope(*PC, CtxI->getFunction());
               }))) {
            for (auto *PotentialCopy : PotentialCopies)
              Worklist.push_back({PotentialCopy, CtxI});
            continue;
          }
        }
      }
    }
 
    // Once a leaf is reached we inform the user through the callback.
    if (!VisitValueCB(*V, CtxI, State, Iteration > 1)) {
      LLVM_DEBUG(dbgs() << "Generic value traversal visit callback failed for: "
                        << *V << "!\n");
      return false;
    }
  } while (!Worklist.empty());
 
  // If we actually used liveness information so we have to record a dependence.
  for (auto &It : LivenessAAs)
    if (It.second.AnyDead)
      A.recordDependence(*It.second.LivenessAA, QueryingAA,
                         DepClassTy::OPTIONAL);
 
  // All values have been visited.
  return true;
}
 
bool AA::getAssumedUnderlyingObjects(Attributor &A, const Value &Ptr,
                                     SmallVectorImpl<Value *> &Objects,
                                     const AbstractAttribute &QueryingAA,
                                     const Instruction *CtxI,
                                     bool &UsedAssumedInformation,
                                     AA::ValueScope VS) {
  auto StripCB = [&](Value *V) { return getUnderlyingObject(V); };
  SmallPtrSet<Value *, 8> SeenObjects;
  auto VisitValueCB = [&SeenObjects](Value &Val, const Instruction *,
                                     SmallVectorImpl<Value *> &Objects,
                                     bool) -> bool {
    if (SeenObjects.insert(&Val).second)
      Objects.push_back(&Val);
    return true;
  };
  if (!genericValueTraversal<decltype(Objects)>(
          A, IRPosition::value(Ptr), QueryingAA, Objects, VisitValueCB, CtxI,
          UsedAssumedInformation, true, 32, StripCB, VS))
    return false;
  return true;
}
 
static const Value *
stripAndAccumulateOffsets(Attributor &A, const AbstractAttribute &QueryingAA,
                          const Value *Val, const DataLayout &DL, APInt &Offset,
                          bool GetMinOffset, bool AllowNonInbounds,
                          bool UseAssumed = false) {
 
  auto AttributorAnalysis = [&](Value &V, APInt &ROffset) -> bool {
    const IRPosition &Pos = IRPosition::value(V);
    // Only track dependence if we are going to use the assumed info.
    const AAValueConstantRange &ValueConstantRangeAA =
        A.getAAFor<AAValueConstantRange>(QueryingAA, Pos,
                                         UseAssumed ? DepClassTy::OPTIONAL
                                                    : DepClassTy::NONE);
    ConstantRange Range = UseAssumed ? ValueConstantRangeAA.getAssumed()
                                     : ValueConstantRangeAA.getKnown();
    if (Range.isFullSet())
      return false;
 
    // We can only use the lower part of the range because the upper part can
    // be higher than what the value can really be.
    if (GetMinOffset)
      ROffset = Range.getSignedMin();
    else
      ROffset = Range.getSignedMax();
    return true;
  };
 
  return Val->stripAndAccumulateConstantOffsets(DL, Offset, AllowNonInbounds,
                                                /* AllowInvariant */ true,
                                                AttributorAnalysis);
}
 
static const Value *
getMinimalBaseOfPointer(Attributor &A, const AbstractAttribute &QueryingAA,
                        const Value *Ptr, int64_t &BytesOffset,
                        const DataLayout &DL, bool AllowNonInbounds = false) {
  APInt OffsetAPInt(DL.getIndexTypeSizeInBits(Ptr->getType()), 0);
  const Value *Base =
      stripAndAccumulateOffsets(A, QueryingAA, Ptr, DL, OffsetAPInt,
                                /* GetMinOffset */ true, AllowNonInbounds);
 
  BytesOffset = OffsetAPInt.getSExtValue();
  return Base;
}
 
/// Clamp the information known for all returned values of a function
/// (identified by \p QueryingAA) into \p S.
template <typename AAType, typename StateType = typename AAType::StateType>
static void clampReturnedValueStates(
    Attributor &A, const AAType &QueryingAA, StateType &S,
    const IRPosition::CallBaseContext *CBContext = nullptr) {
  LLVM_DEBUG(dbgs() << "[Attributor] Clamp return value states for "
                    << QueryingAA << " into " << S << "\n");
 
  assert((QueryingAA.getIRPosition().getPositionKind() ==
              IRPosition::IRP_RETURNED ||
          QueryingAA.getIRPosition().getPositionKind() ==
              IRPosition::IRP_CALL_SITE_RETURNED) &&
         "Can only clamp returned value states for a function returned or call "
         "site returned position!");
 
  // Use an optional state as there might not be any return values and we want
  // to join (IntegerState::operator&) the state of all there are.
  Optional<StateType> T;
 
  // Callback for each possibly returned value.
  auto CheckReturnValue = [&](Value &RV) -> bool {
    const IRPosition &RVPos = IRPosition::value(RV, CBContext);
    const AAType &AA =
        A.getAAFor<AAType>(QueryingAA, RVPos, DepClassTy::REQUIRED);
    LLVM_DEBUG(dbgs() << "[Attributor] RV: " << RV << " AA: " << AA.getAsStr()
                      << " @ " << RVPos << "\n");
    const StateType &AAS = AA.getState();
    if (T.hasValue())
      *T &= AAS;
    else
      T = AAS;
    LLVM_DEBUG(dbgs() << "[Attributor] AA State: " << AAS << " RV State: " << T
                      << "\n");
    return T->isValidState();
  };
 
  if (!A.checkForAllReturnedValues(CheckReturnValue, QueryingAA))
    S.indicatePessimisticFixpoint();
  else if (T.hasValue())
    S ^= *T;
}
 
namespace {
/// Helper class for generic deduction: return value -> returned position.
template <typename AAType, typename BaseType,
          typename StateType = typename BaseType::StateType,
          bool PropagateCallBaseContext = false>
struct AAReturnedFromReturnedValues : public BaseType {
  AAReturnedFromReturnedValues(const IRPosition &IRP, Attributor &A)
      : BaseType(IRP, A) {}
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    StateType S(StateType::getBestState(this->getState()));
    clampReturnedValueStates<AAType, StateType>(
        A, *this, S,
        PropagateCallBaseContext ? this->getCallBaseContext() : nullptr);
    // TODO: If we know we visited all returned values, thus no are assumed
    // dead, we can take the known information from the state T.
    return clampStateAndIndicateChange<StateType>(this->getState(), S);
  }
};
 
/// Clamp the information known at all call sites for a given argument
/// (identified by \p QueryingAA) into \p S.
template <typename AAType, typename StateType = typename AAType::StateType>
static void clampCallSiteArgumentStates(Attributor &A, const AAType &QueryingAA,
                                        StateType &S) {
  LLVM_DEBUG(dbgs() << "[Attributor] Clamp call site argument states for "
                    << QueryingAA << " into " << S << "\n");
 
  assert(QueryingAA.getIRPosition().getPositionKind() ==
             IRPosition::IRP_ARGUMENT &&
         "Can only clamp call site argument states for an argument position!");
 
  // Use an optional state as there might not be any return values and we want
  // to join (IntegerState::operator&) the state of all there are.
  Optional<StateType> T;
 
  // The argument number which is also the call site argument number.
  unsigned ArgNo = QueryingAA.getIRPosition().getCallSiteArgNo();
 
  auto CallSiteCheck = [&](AbstractCallSite ACS) {
    const IRPosition &ACSArgPos = IRPosition::callsite_argument(ACS, ArgNo);
    // Check if a coresponding argument was found or if it is on not associated
    // (which can happen for callback calls).
    if (ACSArgPos.getPositionKind() == IRPosition::IRP_INVALID)
      return false;
 
    const AAType &AA =
        A.getAAFor<AAType>(QueryingAA, ACSArgPos, DepClassTy::REQUIRED);
    LLVM_DEBUG(dbgs() << "[Attributor] ACS: " << *ACS.getInstruction()
                      << " AA: " << AA.getAsStr() << " @" << ACSArgPos << "\n");
    const StateType &AAS = AA.getState();
    if (T.hasValue())
      *T &= AAS;
    else
      T = AAS;
    LLVM_DEBUG(dbgs() << "[Attributor] AA State: " << AAS << " CSA State: " << T
                      << "\n");
    return T->isValidState();
  };
 
  bool UsedAssumedInformation = false;
  if (!A.checkForAllCallSites(CallSiteCheck, QueryingAA, true,
                              UsedAssumedInformation))
    S.indicatePessimisticFixpoint();
  else if (T.hasValue())
    S ^= *T;
}
 
/// This function is the bridge between argument position and the call base
/// context.
template <typename AAType, typename BaseType,
          typename StateType = typename AAType::StateType>
bool getArgumentStateFromCallBaseContext(Attributor &A,
                                         BaseType &QueryingAttribute,
                                         IRPosition &Pos, StateType &State) {
  assert((Pos.getPositionKind() == IRPosition::IRP_ARGUMENT) &&
         "Expected an 'argument' position !");
  const CallBase *CBContext = Pos.getCallBaseContext();
  if (!CBContext)
    return false;
 
  int ArgNo = Pos.getCallSiteArgNo();
  assert(ArgNo >= 0 && "Invalid Arg No!");
 
  const auto &AA = A.getAAFor<AAType>(
      QueryingAttribute, IRPosition::callsite_argument(*CBContext, ArgNo),
      DepClassTy::REQUIRED);
  const StateType &CBArgumentState =
      static_cast<const StateType &>(AA.getState());
 
  LLVM_DEBUG(dbgs() << "[Attributor] Briding Call site context to argument"
                    << "Position:" << Pos << "CB Arg state:" << CBArgumentState
                    << "\n");
 
  // NOTE: If we want to do call site grouping it should happen here.
  State ^= CBArgumentState;
  return true;
}
 
/// Helper class for generic deduction: call site argument -> argument position.
template <typename AAType, typename BaseType,
          typename StateType = typename AAType::StateType,
          bool BridgeCallBaseContext = false>
struct AAArgumentFromCallSiteArguments : public BaseType {
  AAArgumentFromCallSiteArguments(const IRPosition &IRP, Attributor &A)
      : BaseType(IRP, A) {}
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    StateType S = StateType::getBestState(this->getState());
 
    if (BridgeCallBaseContext) {
      bool Success =
          getArgumentStateFromCallBaseContext<AAType, BaseType, StateType>(
              A, *this, this->getIRPosition(), S);
      if (Success)
        return clampStateAndIndicateChange<StateType>(this->getState(), S);
    }
    clampCallSiteArgumentStates<AAType, StateType>(A, *this, S);
 
    // TODO: If we know we visited all incoming values, thus no are assumed
    // dead, we can take the known information from the state T.
    return clampStateAndIndicateChange<StateType>(this->getState(), S);
  }
};
 
/// Helper class for generic replication: function returned -> cs returned.
template <typename AAType, typename BaseType,
          typename StateType = typename BaseType::StateType,
          bool IntroduceCallBaseContext = false>
struct AACallSiteReturnedFromReturned : public BaseType {
  AACallSiteReturnedFromReturned(const IRPosition &IRP, Attributor &A)
      : BaseType(IRP, A) {}
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    assert(this->getIRPosition().getPositionKind() ==
               IRPosition::IRP_CALL_SITE_RETURNED &&
           "Can only wrap function returned positions for call site returned "
           "positions!");
    auto &S = this->getState();
 
    const Function *AssociatedFunction =
        this->getIRPosition().getAssociatedFunction();
    if (!AssociatedFunction)
      return S.indicatePessimisticFixpoint();
 
    CallBase &CBContext = cast<CallBase>(this->getAnchorValue());
    if (IntroduceCallBaseContext)
      LLVM_DEBUG(dbgs() << "[Attributor] Introducing call base context:"
                        << CBContext << "\n");
 
    IRPosition FnPos = IRPosition::returned(
        *AssociatedFunction, IntroduceCallBaseContext ? &CBContext : nullptr);
    const AAType &AA = A.getAAFor<AAType>(*this, FnPos, DepClassTy::REQUIRED);
    return clampStateAndIndicateChange(S, AA.getState());
  }
};
 
/// Helper function to accumulate uses.
template <class AAType, typename StateType = typename AAType::StateType>
static void followUsesInContext(AAType &AA, Attributor &A,
                                MustBeExecutedContextExplorer &Explorer,
                                const Instruction *CtxI,
                                SetVector<const Use *> &Uses,
                                StateType &State) {
  auto EIt = Explorer.begin(CtxI), EEnd = Explorer.end(CtxI);
  for (unsigned u = 0; u < Uses.size(); ++u) {
    const Use *U = Uses[u];
    if (const Instruction *UserI = dyn_cast<Instruction>(U->getUser())) {
      bool Found = Explorer.findInContextOf(UserI, EIt, EEnd);
      if (Found && AA.followUseInMBEC(A, U, UserI, State))
        for (const Use &Us : UserI->uses())
          Uses.insert(&Us);
    }
  }
}
 
/// Use the must-be-executed-context around \p I to add information into \p S.
/// The AAType class is required to have `followUseInMBEC` method with the
/// following signature and behaviour:
///
/// bool followUseInMBEC(Attributor &A, const Use *U, const Instruction *I)
/// U - Underlying use.
/// I - The user of the \p U.
/// Returns true if the value should be tracked transitively.
///
template <class AAType, typename StateType = typename AAType::StateType>
static void followUsesInMBEC(AAType &AA, Attributor &A, StateType &S,
                             Instruction &CtxI) {
 
  // Container for (transitive) uses of the associated value.
  SetVector<const Use *> Uses;
  for (const Use &U : AA.getIRPosition().getAssociatedValue().uses())
    Uses.insert(&U);
 
  MustBeExecutedContextExplorer &Explorer =
      A.getInfoCache().getMustBeExecutedContextExplorer();
 
  followUsesInContext<AAType>(AA, A, Explorer, &CtxI, Uses, S);
 
  if (S.isAtFixpoint())
    return;
 
  SmallVector<const BranchInst *, 4> BrInsts;
  auto Pred = [&](const Instruction *I) {
    if (const BranchInst *Br = dyn_cast<BranchInst>(I))
      if (Br->isConditional())
        BrInsts.push_back(Br);
    return true;
  };
 
  // Here, accumulate conditional branch instructions in the context. We
  // explore the child paths and collect the known states. The disjunction of
  // those states can be merged to its own state. Let ParentState_i be a state
  // to indicate the known information for an i-th branch instruction in the
  // context. ChildStates are created for its successors respectively.
  //
  // ParentS_1 = ChildS_{1, 1} /\ ChildS_{1, 2} /\ ... /\ ChildS_{1, n_1}
  // ParentS_2 = ChildS_{2, 1} /\ ChildS_{2, 2} /\ ... /\ ChildS_{2, n_2}
  //      ...
  // ParentS_m = ChildS_{m, 1} /\ ChildS_{m, 2} /\ ... /\ ChildS_{m, n_m}
  //
  // Known State |= ParentS_1 \/ ParentS_2 \/... \/ ParentS_m
  //
  // FIXME: Currently, recursive branches are not handled. For example, we
  // can't deduce that ptr must be dereferenced in below function.
  //
  // void f(int a, int c, int *ptr) {
  //    if(a)
  //      if (b) {
  //        *ptr = 0;
  //      } else {
  //        *ptr = 1;
  //      }
  //    else {
  //      if (b) {
  //        *ptr = 0;
  //      } else {
  //        *ptr = 1;
  //      }
  //    }
  // }
 
  Explorer.checkForAllContext(&CtxI, Pred);
  for (const BranchInst *Br : BrInsts) {
    StateType ParentState;
 
    // The known state of the parent state is a conjunction of children's
    // known states so it is initialized with a best state.
    ParentState.indicateOptimisticFixpoint();
 
    for (const BasicBlock *BB : Br->successors()) {
      StateType ChildState;
 
      size_t BeforeSize = Uses.size();
      followUsesInContext(AA, A, Explorer, &BB->front(), Uses, ChildState);
 
      // Erase uses which only appear in the child.
      for (auto It = Uses.begin() + BeforeSize; It != Uses.end();)
        It = Uses.erase(It);
 
      ParentState &= ChildState;
    }
 
    // Use only known state.
    S += ParentState;
  }
}
} // namespace
 
/// ------------------------ PointerInfo ---------------------------------------
 
namespace llvm {
namespace AA {
namespace PointerInfo {
 
struct State;
 
} // namespace PointerInfo
} // namespace AA
 
/// Helper for AA::PointerInfo::Acccess DenseMap/Set usage.
template <>
struct DenseMapInfo<AAPointerInfo::Access> : DenseMapInfo<Instruction *> {
  using Access = AAPointerInfo::Access;
  static inline Access getEmptyKey();
  static inline Access getTombstoneKey();
  static unsigned getHashValue(const Access &A);
  static bool isEqual(const Access &LHS, const Access &RHS);
};
 
/// Helper that allows OffsetAndSize as a key in a DenseMap.
template <>
struct DenseMapInfo<AAPointerInfo ::OffsetAndSize>
    : DenseMapInfo<std::pair<int64_t, int64_t>> {};
 
/// Helper for AA::PointerInfo::Acccess DenseMap/Set usage ignoring everythign
/// but the instruction
struct AccessAsInstructionInfo : DenseMapInfo<Instruction *> {
  using Base = DenseMapInfo<Instruction *>;
  using Access = AAPointerInfo::Access;
  static inline Access getEmptyKey();
  static inline Access getTombstoneKey();
  static unsigned getHashValue(const Access &A);
  static bool isEqual(const Access &LHS, const Access &RHS);
};
 
} // namespace llvm
 
/// A type to track pointer/struct usage and accesses for AAPointerInfo.
struct AA::PointerInfo::State : public AbstractState {
 
  ~State() {
    // We do not delete the Accesses objects but need to destroy them still.
    for (auto &It : AccessBins)
      It.second->~Accesses();
  }
 
  /// Return the best possible representable state.
  static State getBestState(const State &SIS) { return State(); }
 
  /// Return the worst possible representable state.
  static State getWorstState(const State &SIS) {
    State R;
    R.indicatePessimisticFixpoint();
    return R;
  }
 
  State() = default;
  State(State &&SIS) : AccessBins(std::move(SIS.AccessBins)) {
    SIS.AccessBins.clear();
  }
 
  const State &getAssumed() const { return *this; }
 
  /// See AbstractState::isValidState().
  bool isValidState() const override { return BS.isValidState(); }
 
  /// See AbstractState::isAtFixpoint().
  bool isAtFixpoint() const override { return BS.isAtFixpoint(); }
 
  /// See AbstractState::indicateOptimisticFixpoint().
  ChangeStatus indicateOptimisticFixpoint() override {
    BS.indicateOptimisticFixpoint();
    return ChangeStatus::UNCHANGED;
  }
 
  /// See AbstractState::indicatePessimisticFixpoint().
  ChangeStatus indicatePessimisticFixpoint() override {
    BS.indicatePessimisticFixpoint();
    return ChangeStatus::CHANGED;
  }
 
  State &operator=(const State &R) {
    if (this == &R)
      return *this;
    BS = R.BS;
    AccessBins = R.AccessBins;
    return *this;
  }
 
  State &operator=(State &&R) {
    if (this == &R)
      return *this;
    std::swap(BS, R.BS);
    std::swap(AccessBins, R.AccessBins);
    return *this;
  }
 
  bool operator==(const State &R) const {
    if (BS != R.BS)
      return false;
    if (AccessBins.size() != R.AccessBins.size())
      return false;
    auto It = begin(), RIt = R.begin(), E = end();
    while (It != E) {
      if (It->getFirst() != RIt->getFirst())
        return false;
      auto &Accs = It->getSecond();
      auto &RAccs = RIt->getSecond();
      if (Accs->size() != RAccs->size())
        return false;
      for (const auto &ZipIt : llvm::zip(*Accs, *RAccs))
        if (std::get<0>(ZipIt) != std::get<1>(ZipIt))
          return false;
      ++It;
      ++RIt;
    }
    return true;
  }
  bool operator!=(const State &R) const { return !(*this == R); }
 
  /// We store accesses in a set with the instruction as key.
  struct Accesses {
    SmallVector<AAPointerInfo::Access, 4> Accesses;
    DenseMap<const Instruction *, unsigned> Map;
 
    unsigned size() const { return Accesses.size(); }
 
    using vec_iterator = decltype(Accesses)::iterator;
    vec_iterator begin() { return Accesses.begin(); }
    vec_iterator end() { return Accesses.end(); }
 
    using iterator = decltype(Map)::const_iterator;
    iterator find(AAPointerInfo::Access &Acc) {
      return Map.find(Acc.getRemoteInst());
    }
    iterator find_end() { return Map.end(); }
 
    AAPointerInfo::Access &get(iterator &It) {
      return Accesses[It->getSecond()];
    }
 
    void insert(AAPointerInfo::Access &Acc) {
      Map[Acc.getRemoteInst()] = Accesses.size();
      Accesses.push_back(Acc);
    }
  };
 
  /// We store all accesses in bins denoted by their offset and size.
  using AccessBinsTy = DenseMap<AAPointerInfo::OffsetAndSize, Accesses *>;
 
  AccessBinsTy::const_iterator begin() const { return AccessBins.begin(); }
  AccessBinsTy::const_iterator end() const { return AccessBins.end(); }
 
protected:
  /// The bins with all the accesses for the associated pointer.
  AccessBinsTy AccessBins;
 
  /// Add a new access to the state at offset \p Offset and with size \p Size.
  /// The access is associated with \p I, writes \p Content (if anything), and
  /// is of kind \p Kind.
  /// \Returns CHANGED, if the state changed, UNCHANGED otherwise.
  ChangeStatus addAccess(Attributor &A, int64_t Offset, int64_t Size,
                         Instruction &I, Optional<Value *> Content,
                         AAPointerInfo::AccessKind Kind, Type *Ty,
                         Instruction *RemoteI = nullptr,
                         Accesses *BinPtr = nullptr) {
    AAPointerInfo::OffsetAndSize Key{Offset, Size};
    Accesses *&Bin = BinPtr ? BinPtr : AccessBins[Key];
    if (!Bin)
      Bin = new (A.Allocator) Accesses;
    AAPointerInfo::Access Acc(&I, RemoteI ? RemoteI : &I, Content, Kind, Ty);
    // Check if we have an access for this instruction in this bin, if not,
    // simply add it.
    auto It = Bin->find(Acc);
    if (It == Bin->find_end()) {
      Bin->insert(Acc);
      return ChangeStatus::CHANGED;
    }
    // If the existing access is the same as then new one, nothing changed.
    AAPointerInfo::Access &Current = Bin->get(It);
    AAPointerInfo::Access Before = Current;
    // The new one will be combined with the existing one.
    Current &= Acc;
    return Current == Before ? ChangeStatus::UNCHANGED : ChangeStatus::CHANGED;
  }
 
  /// See AAPointerInfo::forallInterferingAccesses.
  bool forallInterferingAccesses(
      AAPointerInfo::OffsetAndSize OAS,
      function_ref<bool(const AAPointerInfo::Access &, bool)> CB) const {
    if (!isValidState())
      return false;
 
    for (auto &It : AccessBins) {
      AAPointerInfo::OffsetAndSize ItOAS = It.getFirst();
      if (!OAS.mayOverlap(ItOAS))
        continue;
      bool IsExact = OAS == ItOAS && !OAS.offsetOrSizeAreUnknown();
      for (auto &Access : *It.getSecond())
        if (!CB(Access, IsExact))
          return false;
    }
    return true;
  }
 
  /// See AAPointerInfo::forallInterferingAccesses.
  bool forallInterferingAccesses(
      Instruction &I,
      function_ref<bool(const AAPointerInfo::Access &, bool)> CB) const {
    if (!isValidState())
      return false;
 
    // First find the offset and size of I.
    AAPointerInfo::OffsetAndSize OAS(-1, -1);
    for (auto &It : AccessBins) {
      for (auto &Access : *It.getSecond()) {
        if (Access.getRemoteInst() == &I) {
          OAS = It.getFirst();
          break;
        }
      }
      if (OAS.getSize() != -1)
        break;
    }
    // No access for I was found, we are done.
    if (OAS.getSize() == -1)
      return true;
 
    // Now that we have an offset and size, find all overlapping ones and use
    // the callback on the accesses.
    return forallInterferingAccesses(OAS, CB);
  }
 
private:
  /// State to track fixpoint and validity.
  BooleanState BS;
};
 
namespace {
struct AAPointerInfoImpl
    : public StateWrapper<AA::PointerInfo::State, AAPointerInfo> {
  using BaseTy = StateWrapper<AA::PointerInfo::State, AAPointerInfo>;
  AAPointerInfoImpl(const IRPosition &IRP, Attributor &A) : BaseTy(IRP) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override { AAPointerInfo::initialize(A); }
 
  /// See AbstractAttribute::getAsStr().
  const std::string getAsStr() const override {
    return std::string("PointerInfo ") +
           (isValidState() ? (std::string("#") +
                              std::to_string(AccessBins.size()) + " bins")
                           : "<invalid>");
  }
 
  /// See AbstractAttribute::manifest(...).
  ChangeStatus manifest(Attributor &A) override {
    return AAPointerInfo::manifest(A);
  }
 
  bool forallInterferingAccesses(
      OffsetAndSize OAS,
      function_ref<bool(const AAPointerInfo::Access &, bool)> CB)
      const override {
    return State::forallInterferingAccesses(OAS, CB);
  }
  bool forallInterferingAccesses(
      Attributor &A, const AbstractAttribute &QueryingAA, Instruction &I,
      function_ref<bool(const Access &, bool)> UserCB) const override {
    SmallPtrSet<const Access *, 8> DominatingWrites;
    SmallVector<std::pair<const Access *, bool>, 8> InterferingAccesses;
 
    Function &Scope = *I.getFunction();
    const auto &NoSyncAA = A.getAAFor<AANoSync>(
        QueryingAA, IRPosition::function(Scope), DepClassTy::OPTIONAL);
    const auto *ExecDomainAA = A.lookupAAFor<AAExecutionDomain>(
        IRPosition::function(Scope), &QueryingAA, DepClassTy::OPTIONAL);
    const bool NoSync = NoSyncAA.isAssumedNoSync();
 
    // Helper to determine if we need to consider threading, which we cannot
    // right now. However, if the function is (assumed) nosync or the thread
    // executing all instructions is the main thread only we can ignore
    // threading.
    auto CanIgnoreThreading = [&](const Instruction &I) -> bool {
      if (NoSync)
        return true;
      if (ExecDomainAA && ExecDomainAA->isExecutedByInitialThreadOnly(I))
        return true;
      return false;
    };
 
    // Helper to determine if the access is executed by the same thread as the
    // load, for now it is sufficient to avoid any potential threading effects
    // as we cannot deal with them anyway.
    auto IsSameThreadAsLoad = [&](const Access &Acc) -> bool {
      return CanIgnoreThreading(*Acc.getLocalInst());
    };
 
    // TODO: Use inter-procedural reachability and dominance.
    const auto &NoRecurseAA = A.getAAFor<AANoRecurse>(
        QueryingAA, IRPosition::function(Scope), DepClassTy::OPTIONAL);
 
    const bool FindInterferingWrites = I.mayReadFromMemory();
    const bool FindInterferingReads = I.mayWriteToMemory();
    const bool UseDominanceReasoning = FindInterferingWrites;
    const bool CanUseCFGResoning = CanIgnoreThreading(I);
    InformationCache &InfoCache = A.getInfoCache();
    const DominatorTree *DT =
        NoRecurseAA.isKnownNoRecurse() && UseDominanceReasoning
            ? InfoCache.getAnalysisResultForFunction<DominatorTreeAnalysis>(
                  Scope)
            : nullptr;
 
    enum GPUAddressSpace : unsigned {
      Generic = 0,
      Global = 1,
      Shared = 3,
      Constant = 4,
      Local = 5,
    };
 
    // Helper to check if a value has "kernel lifetime", that is it will not
    // outlive a GPU kernel. This is true for shared, constant, and local
    // globals on AMD and NVIDIA GPUs.
    auto HasKernelLifetime = [&](Value *V, Module &M) {
      Triple T(M.getTargetTriple());
      if (!(T.isAMDGPU() || T.isNVPTX()))
        return false;
      switch (V->getType()->getPointerAddressSpace()) {
      case GPUAddressSpace::Shared:
      case GPUAddressSpace::Constant:
      case GPUAddressSpace::Local:
        return true;
      default:
        return false;
      };
    };
 
    // The IsLiveInCalleeCB will be used by the AA::isPotentiallyReachable query
    // to determine if we should look at reachability from the callee. For
    // certain pointers we know the lifetime and we do not have to step into the
    // callee to determine reachability as the pointer would be dead in the
    // callee. See the conditional initialization below.
    std::function<bool(const Function &)> IsLiveInCalleeCB;
 
    if (auto *AI = dyn_cast<AllocaInst>(&getAssociatedValue())) {
      // If the alloca containing function is not recursive the alloca
      // must be dead in the callee.
      const Function *AIFn = AI->getFunction();
      const auto &NoRecurseAA = A.getAAFor<AANoRecurse>(
          *this, IRPosition::function(*AIFn), DepClassTy::OPTIONAL);
      if (NoRecurseAA.isAssumedNoRecurse()) {
        IsLiveInCalleeCB = [AIFn](const Function &Fn) { return AIFn != &Fn; };
      }
    } else if (auto *GV = dyn_cast<GlobalValue>(&getAssociatedValue())) {
      // If the global has kernel lifetime we can stop if we reach a kernel
      // as it is "dead" in the (unknown) callees.
      if (HasKernelLifetime(GV, *GV->getParent()))
        IsLiveInCalleeCB = [](const Function &Fn) {
          return !Fn.hasFnAttribute("kernel");
        };
    }
 
    auto AccessCB = [&](const Access &Acc, bool Exact) {
      if ((!FindInterferingWrites || !Acc.isWrite()) &&
          (!FindInterferingReads || !Acc.isRead()))
        return true;
 
      // For now we only filter accesses based on CFG reasoning which does not
      // work yet if we have threading effects, or the access is complicated.
      if (CanUseCFGResoning) {
        if ((!Acc.isWrite() ||
             !AA::isPotentiallyReachable(A, *Acc.getLocalInst(), I, QueryingAA,
                                         IsLiveInCalleeCB)) &&
            (!Acc.isRead() ||
             !AA::isPotentiallyReachable(A, I, *Acc.getLocalInst(), QueryingAA,
                                         IsLiveInCalleeCB)))
          return true;
        if (DT && Exact && (Acc.getLocalInst()->getFunction() == &Scope) &&
            IsSameThreadAsLoad(Acc)) {
          if (DT->dominates(Acc.getLocalInst(), &I))
            DominatingWrites.insert(&Acc);
        }
      }
 
      InterferingAccesses.push_back({&Acc, Exact});
      return true;
    };
    if (!State::forallInterferingAccesses(I, AccessCB))
      return false;
 
    // If we cannot use CFG reasoning we only filter the non-write accesses
    // and are done here.
    if (!CanUseCFGResoning) {
      for (auto &It : InterferingAccesses)
        if (!UserCB(*It.first, It.second))
          return false;
      return true;
    }
 
    // Helper to determine if we can skip a specific write access. This is in
    // the worst case quadratic as we are looking for another write that will
    // hide the effect of this one.
    auto CanSkipAccess = [&](const Access &Acc, bool Exact) {
      if (!IsSameThreadAsLoad(Acc))
        return false;
      if (!DominatingWrites.count(&Acc))
        return false;
      for (const Access *DomAcc : DominatingWrites) {
        assert(Acc.getLocalInst()->getFunction() ==
                   DomAcc->getLocalInst()->getFunction() &&
               "Expected dominating writes to be in the same function!");
 
        if (DomAcc != &Acc &&
            DT->dominates(Acc.getLocalInst(), DomAcc->getLocalInst())) {
          return true;
        }
      }
      return false;
    };
 
    // Run the user callback on all accesses we cannot skip and return if that
    // succeeded for all or not.
    unsigned NumInterferingAccesses = InterferingAccesses.size();
    for (auto &It : InterferingAccesses) {
      if (!DT || NumInterferingAccesses > MaxInterferingAccesses ||
          !CanSkipAccess(*It.first, It.second)) {
        if (!UserCB(*It.first, It.second))
          return false;
      }
    }
    return true;
  }
 
  ChangeStatus translateAndAddCalleeState(Attributor &A,
                                          const AAPointerInfo &CalleeAA,
                                          int64_t CallArgOffset, CallBase &CB) {
    using namespace AA::PointerInfo;
    if (!CalleeAA.getState().isValidState() || !isValidState())
      return indicatePessimisticFixpoint();
 
    const auto &CalleeImplAA = static_cast<const AAPointerInfoImpl &>(CalleeAA);
    bool IsByval = CalleeImplAA.getAssociatedArgument()->hasByValAttr();
 
    // Combine the accesses bin by bin.
    ChangeStatus Changed = ChangeStatus::UNCHANGED;
    for (auto &It : CalleeImplAA.getState()) {
      OffsetAndSize OAS = OffsetAndSize::getUnknown();
      if (CallArgOffset != OffsetAndSize::Unknown)
        OAS = OffsetAndSize(It.first.getOffset() + CallArgOffset,
                            It.first.getSize());
      Accesses *Bin = AccessBins[OAS];
      for (const AAPointerInfo::Access &RAcc : *It.second) {
        if (IsByval && !RAcc.isRead())
          continue;
        bool UsedAssumedInformation = false;
        Optional<Value *> Content = A.translateArgumentToCallSiteContent(
            RAcc.getContent(), CB, *this, UsedAssumedInformation);
        AccessKind AK =
            AccessKind(RAcc.getKind() & (IsByval ? AccessKind::AK_READ
                                                 : AccessKind::AK_READ_WRITE));
        Changed =
            Changed | addAccess(A, OAS.getOffset(), OAS.getSize(), CB, Content,
                                AK, RAcc.getType(), RAcc.getRemoteInst(), Bin);
      }
    }
    return Changed;
  }
 
  /// Statistic tracking for all AAPointerInfo implementations.
  /// See AbstractAttribute::trackStatistics().
  void trackPointerInfoStatistics(const IRPosition &IRP) const {}
};
 
struct AAPointerInfoFloating : public AAPointerInfoImpl {
  using AccessKind = AAPointerInfo::AccessKind;
  AAPointerInfoFloating(const IRPosition &IRP, Attributor &A)
      : AAPointerInfoImpl(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override { AAPointerInfoImpl::initialize(A); }
 
  /// Deal with an access and signal if it was handled successfully.
  bool handleAccess(Attributor &A, Instruction &I, Value &Ptr,
                    Optional<Value *> Content, AccessKind Kind, int64_t Offset,
                    ChangeStatus &Changed, Type *Ty,
                    int64_t Size = OffsetAndSize::Unknown) {
    using namespace AA::PointerInfo;
    // No need to find a size if one is given or the offset is unknown.
    if (Offset != OffsetAndSize::Unknown && Size == OffsetAndSize::Unknown &&
        Ty) {
      const DataLayout &DL = A.getDataLayout();
      TypeSize AccessSize = DL.getTypeStoreSize(Ty);
      if (!AccessSize.isScalable())
        Size = AccessSize.getFixedSize();
    }
    Changed = Changed | addAccess(A, Offset, Size, I, Content, Kind, Ty);
    return true;
  };
 
  /// Helper struct, will support ranges eventually.
  struct OffsetInfo {
    int64_t Offset = OffsetAndSize::Unknown;
 
    bool operator==(const OffsetInfo &OI) const { return Offset == OI.Offset; }
  };
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    using namespace AA::PointerInfo;
    ChangeStatus Changed = ChangeStatus::UNCHANGED;
    Value &AssociatedValue = getAssociatedValue();
 
    const DataLayout &DL = A.getDataLayout();
    DenseMap<Value *, OffsetInfo> OffsetInfoMap;
    OffsetInfoMap[&AssociatedValue] = OffsetInfo{0};
 
    auto HandlePassthroughUser = [&](Value *Usr, OffsetInfo PtrOI,
                                     bool &Follow) {
      OffsetInfo &UsrOI = OffsetInfoMap[Usr];
      UsrOI = PtrOI;
      Follow = true;
      return true;
    };
 
    const auto *TLI = getAnchorScope()
                          ? A.getInfoCache().getTargetLibraryInfoForFunction(
                                *getAnchorScope())
                          : nullptr;
    auto UsePred = [&](const Use &U, bool &Follow) -> bool {
      Value *CurPtr = U.get();
      User *Usr = U.getUser();
      LLVM_DEBUG(dbgs() << "[AAPointerInfo] Analyze " << *CurPtr << " in "
                        << *Usr << "\n");
      assert(OffsetInfoMap.count(CurPtr) &&
             "The current pointer offset should have been seeded!");
 
      if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Usr)) {
        if (CE->isCast())
          return HandlePassthroughUser(Usr, OffsetInfoMap[CurPtr], Follow);
        if (CE->isCompare())
          return true;
        if (!isa<GEPOperator>(CE)) {
          LLVM_DEBUG(dbgs() << "[AAPointerInfo] Unhandled constant user " << *CE
                            << "\n");
          return false;
        }
      }
      if (auto *GEP = dyn_cast<GEPOperator>(Usr)) {
        // Note the order here, the Usr access might change the map, CurPtr is
        // already in it though.
        OffsetInfo &UsrOI = OffsetInfoMap[Usr];
        OffsetInfo &PtrOI = OffsetInfoMap[CurPtr];
        UsrOI = PtrOI;
 
        // TODO: Use range information.
        if (PtrOI.Offset == OffsetAndSize::Unknown ||
            !GEP->hasAllConstantIndices()) {
          UsrOI.Offset = OffsetAndSize::Unknown;
          Follow = true;
          return true;
        }
 
        SmallVector<Value *, 8> Indices;
        for (Use &Idx : GEP->indices()) {
          if (auto *CIdx = dyn_cast<ConstantInt>(Idx)) {
            Indices.push_back(CIdx);
            continue;
          }
 
          LLVM_DEBUG(dbgs() << "[AAPointerInfo] Non constant GEP index " << *GEP
                            << " : " << *Idx << "\n");
          return false;
        }
        UsrOI.Offset = PtrOI.Offset + DL.getIndexedOffsetInType(
                                          GEP->getSourceElementType(), Indices);
        Follow = true;
        return true;
      }
      if (isa<CastInst>(Usr) || isa<SelectInst>(Usr))
        return HandlePassthroughUser(Usr, OffsetInfoMap[CurPtr], Follow);
 
      // For PHIs we need to take care of the recurrence explicitly as the value
      // might change while we iterate through a loop. For now, we give up if
      // the PHI is not invariant.
      if (isa<PHINode>(Usr)) {
        // Note the order here, the Usr access might change the map, CurPtr is
        // already in it though.
        OffsetInfo &UsrOI = OffsetInfoMap[Usr];
        OffsetInfo &PtrOI = OffsetInfoMap[CurPtr];
        // Check if the PHI is invariant (so far).
        if (UsrOI == PtrOI)
          return true;
 
        // Check if the PHI operand has already an unknown offset as we can't
        // improve on that anymore.
        if (PtrOI.Offset == OffsetAndSize::Unknown) {
          UsrOI = PtrOI;
          Follow = true;
          return true;
        }
 
        // Check if the PHI operand is not dependent on the PHI itself.
        // TODO: This is not great as we look at the pointer type. However, it
        // is unclear where the Offset size comes from with typeless pointers.
        APInt Offset(
            DL.getIndexSizeInBits(CurPtr->getType()->getPointerAddressSpace()),
            0);
        if (&AssociatedValue == CurPtr->stripAndAccumulateConstantOffsets(
                                    DL, Offset, /* AllowNonInbounds */ true)) {
          if (Offset != PtrOI.Offset) {
            LLVM_DEBUG(dbgs()
                       << "[AAPointerInfo] PHI operand pointer offset mismatch "
                       << *CurPtr << " in " << *Usr << "\n");
            return false;
          }
          return HandlePassthroughUser(Usr, PtrOI, Follow);
        }
 
        // TODO: Approximate in case we know the direction of the recurrence.
        LLVM_DEBUG(dbgs() << "[AAPointerInfo] PHI operand is too complex "
                          << *CurPtr << " in " << *Usr << "\n");
        UsrOI = PtrOI;
        UsrOI.Offset = OffsetAndSize::Unknown;
        Follow = true;
        return true;
      }
 
      if (auto *LoadI = dyn_cast<LoadInst>(Usr))
        return handleAccess(A, *LoadI, *CurPtr, /* Content */ nullptr,
                            AccessKind::AK_READ, OffsetInfoMap[CurPtr].Offset,
                            Changed, LoadI->getType());
      if (auto *StoreI = dyn_cast<StoreInst>(Usr)) {
        if (StoreI->getValueOperand() == CurPtr) {
          LLVM_DEBUG(dbgs() << "[AAPointerInfo] Escaping use in store "
                            << *StoreI << "\n");
          return false;
        }
        bool UsedAssumedInformation = false;
        Optional<Value *> Content = A.getAssumedSimplified(
            *StoreI->getValueOperand(), *this, UsedAssumedInformation);
        return handleAccess(A, *StoreI, *CurPtr, Content, AccessKind::AK_WRITE,
                            OffsetInfoMap[CurPtr].Offset, Changed,
                            StoreI->getValueOperand()->getType());
      }
      if (auto *CB = dyn_cast<CallBase>(Usr)) {
        if (CB->isLifetimeStartOrEnd())
          return true;
        if (TLI && isFreeCall(CB, TLI))
          return true;
        if (CB->isArgOperand(&U)) {
          unsigned ArgNo = CB->getArgOperandNo(&U);
          const auto &CSArgPI = A.getAAFor<AAPointerInfo>(
              *this, IRPosition::callsite_argument(*CB, ArgNo),
              DepClassTy::REQUIRED);
          Changed = translateAndAddCalleeState(
                        A, CSArgPI, OffsetInfoMap[CurPtr].Offset, *CB) |
                    Changed;
          return true;
        }
        LLVM_DEBUG(dbgs() << "[AAPointerInfo] Call user not handled " << *CB
                          << "\n");
        // TODO: Allow some call uses
        return false;
      }
 
      LLVM_DEBUG(dbgs() << "[AAPointerInfo] User not handled " << *Usr << "\n");
      return false;
    };
    auto EquivalentUseCB = [&](const Use &OldU, const Use &NewU) {
      if (OffsetInfoMap.count(NewU))
        return OffsetInfoMap[NewU] == OffsetInfoMap[OldU];
      OffsetInfoMap[NewU] = OffsetInfoMap[OldU];
      return true;
    };
    if (!A.checkForAllUses(UsePred, *this, AssociatedValue,
                           /* CheckBBLivenessOnly */ true, DepClassTy::OPTIONAL,
                           /* IgnoreDroppableUses */ true, EquivalentUseCB))
      return indicatePessimisticFixpoint();
 
    LLVM_DEBUG({
      dbgs() << "Accesses by bin after update:\n";
      for (auto &It : AccessBins) {
        dbgs() << "[" << It.first.getOffset() << "-"
               << It.first.getOffset() + It.first.getSize()
               << "] : " << It.getSecond()->size() << "\n";
        for (auto &Acc : *It.getSecond()) {
          dbgs() << "     - " << Acc.getKind() << " - " << *Acc.getLocalInst()
                 << "\n";
          if (Acc.getLocalInst() != Acc.getRemoteInst())
            dbgs() << "     -->                         "
                   << *Acc.getRemoteInst() << "\n";
          if (!Acc.isWrittenValueYetUndetermined()) {
            if (Acc.getWrittenValue())
              dbgs() << "       - c: " << *Acc.getWrittenValue() << "\n";
            else
              dbgs() << "       - c: <unknown>\n";
          }
        }
      }
    });
 
    return Changed;
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override {
    AAPointerInfoImpl::trackPointerInfoStatistics(getIRPosition());
  }
};
 
struct AAPointerInfoReturned final : AAPointerInfoImpl {
  AAPointerInfoReturned(const IRPosition &IRP, Attributor &A)
      : AAPointerInfoImpl(IRP, A) {}
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    return indicatePessimisticFixpoint();
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override {
    AAPointerInfoImpl::trackPointerInfoStatistics(getIRPosition());
  }
};
 
struct AAPointerInfoArgument final : AAPointerInfoFloating {
  AAPointerInfoArgument(const IRPosition &IRP, Attributor &A)
      : AAPointerInfoFloating(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    AAPointerInfoFloating::initialize(A);
    if (getAnchorScope()->isDeclaration())
      indicatePessimisticFixpoint();
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override {
    AAPointerInfoImpl::trackPointerInfoStatistics(getIRPosition());
  }
};
 
struct AAPointerInfoCallSiteArgument final : AAPointerInfoFloating {
  AAPointerInfoCallSiteArgument(const IRPosition &IRP, Attributor &A)
      : AAPointerInfoFloating(IRP, A) {}
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    using namespace AA::PointerInfo;
    // We handle memory intrinsics explicitly, at least the first (=
    // destination) and second (=source) arguments as we know how they are
    // accessed.
    if (auto *MI = dyn_cast_or_null<MemIntrinsic>(getCtxI())) {
      ConstantInt *Length = dyn_cast<ConstantInt>(MI->getLength());
      int64_t LengthVal = OffsetAndSize::Unknown;
      if (Length)
        LengthVal = Length->getSExtValue();
      Value &Ptr = getAssociatedValue();
      unsigned ArgNo = getIRPosition().getCallSiteArgNo();
      ChangeStatus Changed = ChangeStatus::UNCHANGED;
      if (ArgNo == 0) {
        handleAccess(A, *MI, Ptr, nullptr, AccessKind::AK_WRITE, 0, Changed,
                     nullptr, LengthVal);
      } else if (ArgNo == 1) {
        handleAccess(A, *MI, Ptr, nullptr, AccessKind::AK_READ, 0, Changed,
                     nullptr, LengthVal);
      } else {
        LLVM_DEBUG(dbgs() << "[AAPointerInfo] Unhandled memory intrinsic "
                          << *MI << "\n");
        return indicatePessimisticFixpoint();
      }
      return Changed;
    }
 
    // TODO: Once we have call site specific value information we can provide
    //       call site specific liveness information and then it makes
    //       sense to specialize attributes for call sites arguments instead of
    //       redirecting requests to the callee argument.
    Argument *Arg = getAssociatedArgument();
    if (!Arg)
      return indicatePessimisticFixpoint();
    const IRPosition &ArgPos = IRPosition::argument(*Arg);
    auto &ArgAA =
        A.getAAFor<AAPointerInfo>(*this, ArgPos, DepClassTy::REQUIRED);
    return translateAndAddCalleeState(A, ArgAA, 0, *cast<CallBase>(getCtxI()));
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override {
    AAPointerInfoImpl::trackPointerInfoStatistics(getIRPosition());
  }
};
 
struct AAPointerInfoCallSiteReturned final : AAPointerInfoFloating {
  AAPointerInfoCallSiteReturned(const IRPosition &IRP, Attributor &A)
      : AAPointerInfoFloating(IRP, A) {}
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override {
    AAPointerInfoImpl::trackPointerInfoStatistics(getIRPosition());
  }
};
} // namespace
 
/// -----------------------NoUnwind Function Attribute--------------------------
 
namespace {
struct AANoUnwindImpl : AANoUnwind {
  AANoUnwindImpl(const IRPosition &IRP, Attributor &A) : AANoUnwind(IRP, A) {}
 
  const std::string getAsStr() const override {
    return getAssumed() ? "nounwind" : "may-unwind";
  }
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    auto Opcodes = {
        (unsigned)Instruction::Invoke,      (unsigned)Instruction::CallBr,
        (unsigned)Instruction::Call,        (unsigned)Instruction::CleanupRet,
        (unsigned)Instruction::CatchSwitch, (unsigned)Instruction::Resume};
 
    auto CheckForNoUnwind = [&](Instruction &I) {
      if (!I.mayThrow())
        return true;
 
      if (const auto *CB = dyn_cast<CallBase>(&I)) {
        const auto &NoUnwindAA = A.getAAFor<AANoUnwind>(
            *this, IRPosition::callsite_function(*CB), DepClassTy::REQUIRED);
        return NoUnwindAA.isAssumedNoUnwind();
      }
      return false;
    };
 
    bool UsedAssumedInformation = false;
    if (!A.checkForAllInstructions(CheckForNoUnwind, *this, Opcodes,
                                   UsedAssumedInformation))
      return indicatePessimisticFixpoint();
 
    return ChangeStatus::UNCHANGED;
  }
};
 
struct AANoUnwindFunction final : public AANoUnwindImpl {
  AANoUnwindFunction(const IRPosition &IRP, Attributor &A)
      : AANoUnwindImpl(IRP, A) {}
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(nounwind) }
};
 
/// NoUnwind attribute deduction for a call sites.
struct AANoUnwindCallSite final : AANoUnwindImpl {
  AANoUnwindCallSite(const IRPosition &IRP, Attributor &A)
      : AANoUnwindImpl(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    AANoUnwindImpl::initialize(A);
    Function *F = getAssociatedFunction();
    if (!F || F->isDeclaration())
      indicatePessimisticFixpoint();
  }
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    // TODO: Once we have call site specific value information we can provide
    //       call site specific liveness information and then it makes
    //       sense to specialize attributes for call sites arguments instead of
    //       redirecting requests to the callee argument.
    Function *F = getAssociatedFunction();
    const IRPosition &FnPos = IRPosition::function(*F);
    auto &FnAA = A.getAAFor<AANoUnwind>(*this, FnPos, DepClassTy::REQUIRED);
    return clampStateAndIndicateChange(getState(), FnAA.getState());
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(nounwind); }
};
} // namespace
 
/// --------------------- Function Return Values -------------------------------
 
namespace {
/// "Attribute" that collects all potential returned values and the return
/// instructions that they arise from.
///
/// If there is a unique returned value R, the manifest method will:
///   - mark R with the "returned" attribute, if R is an argument.
class AAReturnedValuesImpl : public AAReturnedValues, public AbstractState {
 
  /// Mapping of values potentially returned by the associated function to the
  /// return instructions that might return them.
  MapVector<Value *, SmallSetVector<ReturnInst *, 4>> ReturnedValues;
 
  /// State flags
  ///
  ///{
  bool IsFixed = false;
  bool IsValidState = true;
  ///}
 
public:
  AAReturnedValuesImpl(const IRPosition &IRP, Attributor &A)
      : AAReturnedValues(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    // Reset the state.
    IsFixed = false;
    IsValidState = true;
    ReturnedValues.clear();
 
    Function *F = getAssociatedFunction();
    if (!F || F->isDeclaration()) {
      indicatePessimisticFixpoint();
      return;
    }
    assert(!F->getReturnType()->isVoidTy() &&
           "Did not expect a void return type!");
 
    // The map from instruction opcodes to those instructions in the function.
    auto &OpcodeInstMap = A.getInfoCache().getOpcodeInstMapForFunction(*F);
 
    // Look through all arguments, if one is marked as returned we are done.
    for (Argument &Arg : F->args()) {
      if (Arg.hasReturnedAttr()) {
        auto &ReturnInstSet = ReturnedValues[&Arg];
        if (auto *Insts = OpcodeInstMap.lookup(Instruction::Ret))
          for (Instruction *RI : *Insts)
            ReturnInstSet.insert(cast<ReturnInst>(RI));
 
        indicateOptimisticFixpoint();
        return;
      }
    }
 
    if (!A.isFunctionIPOAmendable(*F))
      indicatePessimisticFixpoint();
  }
 
  /// See AbstractAttribute::manifest(...).
  ChangeStatus manifest(Attributor &A) override;
 
  /// See AbstractAttribute::getState(...).
  AbstractState &getState() override { return *this; }
 
  /// See AbstractAttribute::getState(...).
  const AbstractState &getState() const override { return *this; }
 
  /// See AbstractAttribute::updateImpl(Attributor &A).
  ChangeStatus updateImpl(Attributor &A) override;
 
  llvm::iterator_range<iterator> returned_values() override {
    return llvm::make_range(ReturnedValues.begin(), ReturnedValues.end());
  }
 
  llvm::iterator_range<const_iterator> returned_values() const override {
    return llvm::make_range(ReturnedValues.begin(), ReturnedValues.end());
  }
 
  /// Return the number of potential return values, -1 if unknown.
  size_t getNumReturnValues() const override {
    return isValidState() ? ReturnedValues.size() : -1;
  }
 
  /// Return an assumed unique return value if a single candidate is found. If
  /// there cannot be one, return a nullptr. If it is not clear yet, return the
  /// Optional::NoneType.
  Optional<Value *> getAssumedUniqueReturnValue(Attributor &A) const;
 
  /// See AbstractState::checkForAllReturnedValues(...).
  bool checkForAllReturnedValuesAndReturnInsts(
      function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)> Pred)
      const override;
 
  /// Pretty print the attribute similar to the IR representation.
  const std::string getAsStr() const override;
 
  /// See AbstractState::isAtFixpoint().
  bool isAtFixpoint() const override { return IsFixed; }
 
  /// See AbstractState::isValidState().
  bool isValidState() const override { return IsValidState; }
 
  /// See AbstractState::indicateOptimisticFixpoint(...).
  ChangeStatus indicateOptimisticFixpoint() override {
    IsFixed = true;
    return ChangeStatus::UNCHANGED;
  }
 
  ChangeStatus indicatePessimisticFixpoint() override {
    IsFixed = true;
    IsValidState = false;
    return ChangeStatus::CHANGED;
  }
};
 
ChangeStatus AAReturnedValuesImpl::manifest(Attributor &A) {
  ChangeStatus Changed = ChangeStatus::UNCHANGED;
 
  // Bookkeeping.
  assert(isValidState());
  STATS_DECLTRACK(KnownReturnValues, FunctionReturn,
                  "Number of function with known return values");
 
  // Check if we have an assumed unique return value that we could manifest.
  Optional<Value *> UniqueRV = getAssumedUniqueReturnValue(A);
 
  if (!UniqueRV.hasValue() || !UniqueRV.getValue())
    return Changed;
 
  // Bookkeeping.
  STATS_DECLTRACK(UniqueReturnValue, FunctionReturn,
                  "Number of function with unique return");
  // If the assumed unique return value is an argument, annotate it.
  if (auto *UniqueRVArg = dyn_cast<Argument>(UniqueRV.getValue())) {
    if (UniqueRVArg->getType()->canLosslesslyBitCastTo(
            getAssociatedFunction()->getReturnType())) {
      getIRPosition() = IRPosition::argument(*UniqueRVArg);
      Changed = IRAttribute::manifest(A);
    }
  }
  return Changed;
}
 
const std::string AAReturnedValuesImpl::getAsStr() const {
  return (isAtFixpoint() ? "returns(#" : "may-return(#") +
         (isValidState() ? std::to_string(getNumReturnValues()) : "?") + ")";
}
 
Optional<Value *>
AAReturnedValuesImpl::getAssumedUniqueReturnValue(Attributor &A) const {
  // If checkForAllReturnedValues provides a unique value, ignoring potential
  // undef values that can also be present, it is assumed to be the actual
  // return value and forwarded to the caller of this method. If there are
  // multiple, a nullptr is returned indicating there cannot be a unique
  // returned value.
  Optional<Value *> UniqueRV;
  Type *Ty = getAssociatedFunction()->getReturnType();
 
  auto Pred = [&](Value &RV) -> bool {
    UniqueRV = AA::combineOptionalValuesInAAValueLatice(UniqueRV, &RV, Ty);
    return UniqueRV != Optional<Value *>(nullptr);
  };
 
  if (!A.checkForAllReturnedValues(Pred, *this))
    UniqueRV = nullptr;
 
  return UniqueRV;
}
 
bool AAReturnedValuesImpl::checkForAllReturnedValuesAndReturnInsts(
    function_ref<bool(Value &, const SmallSetVector<ReturnInst *, 4> &)> Pred)
    const {
  if (!isValidState())
    return false;
 
  // Check all returned values but ignore call sites as long as we have not
  // encountered an overdefined one during an update.
  for (auto &It : ReturnedValues) {
    Value *RV = It.first;
    if (!Pred(*RV, It.second))
      return false;
  }
 
  return true;
}
 
ChangeStatus AAReturnedValuesImpl::updateImpl(Attributor &A) {
  ChangeStatus Changed = ChangeStatus::UNCHANGED;
 
  auto ReturnValueCB = [&](Value &V, const Instruction *CtxI, ReturnInst &Ret,
                           bool) -> bool {
    assert(AA::isValidInScope(V, Ret.getFunction()) &&
           "Assumed returned value should be valid in function scope!");
    if (ReturnedValues[&V].insert(&Ret))
      Changed = ChangeStatus::CHANGED;
    return true;
  };
 
  bool UsedAssumedInformation = false;
  auto ReturnInstCB = [&](Instruction &I) {
    ReturnInst &Ret = cast<ReturnInst>(I);
    return genericValueTraversal<ReturnInst>(
        A, IRPosition::value(*Ret.getReturnValue()), *this, Ret, ReturnValueCB,
        &I, UsedAssumedInformation, /* UseValueSimplify */ true,
        /* MaxValues */ 16,
        /* StripCB */ nullptr, AA::Intraprocedural);
  };
 
  // Discover returned values from all live returned instructions in the
  // associated function.
  if (!A.checkForAllInstructions(ReturnInstCB, *this, {Instruction::Ret},
                                 UsedAssumedInformation))
    return indicatePessimisticFixpoint();
  return Changed;
}
 
struct AAReturnedValuesFunction final : public AAReturnedValuesImpl {
  AAReturnedValuesFunction(const IRPosition &IRP, Attributor &A)
      : AAReturnedValuesImpl(IRP, A) {}
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(returned) }
};
 
/// Returned values information for a call sites.
struct AAReturnedValuesCallSite final : AAReturnedValuesImpl {
  AAReturnedValuesCallSite(const IRPosition &IRP, Attributor &A)
      : AAReturnedValuesImpl(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    // TODO: Once we have call site specific value information we can provide
    //       call site specific liveness information and then it makes
    //       sense to specialize attributes for call sites instead of
    //       redirecting requests to the callee.
    llvm_unreachable("Abstract attributes for returned values are not "
                     "supported for call sites yet!");
  }
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    return indicatePessimisticFixpoint();
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override {}
};
} // namespace
 
/// ------------------------ NoSync Function Attribute -------------------------
 
bool AANoSync::isNonRelaxedAtomic(const Instruction *I) {
  if (!I->isAtomic())
    return false;
 
  if (auto *FI = dyn_cast<FenceInst>(I))
    // All legal orderings for fence are stronger than monotonic.
    return FI->getSyncScopeID() != SyncScope::SingleThread;
  if (auto *AI = dyn_cast<AtomicCmpXchgInst>(I)) {
    // Unordered is not a legal ordering for cmpxchg.
    return (AI->getSuccessOrdering() != AtomicOrdering::Monotonic ||
            AI->getFailureOrdering() != AtomicOrdering::Monotonic);
  }
 
  AtomicOrdering Ordering;
  switch (I->getOpcode()) {
  case Instruction::AtomicRMW:
    Ordering = cast<AtomicRMWInst>(I)->getOrdering();
    break;
  case Instruction::Store:
    Ordering = cast<StoreInst>(I)->getOrdering();
    break;
  case Instruction::Load:
    Ordering = cast<LoadInst>(I)->getOrdering();
    break;
  default:
    llvm_unreachable(
        "New atomic operations need to be known in the attributor.");
  }
 
  return (Ordering != AtomicOrdering::Unordered &&
          Ordering != AtomicOrdering::Monotonic);
}
 
/// Return true if this intrinsic is nosync.  This is only used for intrinsics
/// which would be nosync except that they have a volatile flag.  All other
/// intrinsics are simply annotated with the nosync attribute in Intrinsics.td.
bool AANoSync::isNoSyncIntrinsic(const Instruction *I) {
  if (auto *MI = dyn_cast<MemIntrinsic>(I))
    return !MI->isVolatile();
  return false;
}
 
namespace {
struct AANoSyncImpl : AANoSync {
  AANoSyncImpl(const IRPosition &IRP, Attributor &A) : AANoSync(IRP, A) {}
 
  const std::string getAsStr() const override {
    return getAssumed() ? "nosync" : "may-sync";
  }
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override;
};
 
ChangeStatus AANoSyncImpl::updateImpl(Attributor &A) {
 
  auto CheckRWInstForNoSync = [&](Instruction &I) {
    return AA::isNoSyncInst(A, I, *this);
  };
 
  auto CheckForNoSync = [&](Instruction &I) {
    // At this point we handled all read/write effects and they are all
    // nosync, so they can be skipped.
    if (I.mayReadOrWriteMemory())
      return true;
 
    // non-convergent and readnone imply nosync.
    return !cast<CallBase>(I).isConvergent();
  };
 
  bool UsedAssumedInformation = false;
  if (!A.checkForAllReadWriteInstructions(CheckRWInstForNoSync, *this,
                                          UsedAssumedInformation) ||
      !A.checkForAllCallLikeInstructions(CheckForNoSync, *this,
                                         UsedAssumedInformation))
    return indicatePessimisticFixpoint();
 
  return ChangeStatus::UNCHANGED;
}
 
struct AANoSyncFunction final : public AANoSyncImpl {
  AANoSyncFunction(const IRPosition &IRP, Attributor &A)
      : AANoSyncImpl(IRP, A) {}
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(nosync) }
};
 
/// NoSync attribute deduction for a call sites.
struct AANoSyncCallSite final : AANoSyncImpl {
  AANoSyncCallSite(const IRPosition &IRP, Attributor &A)
      : AANoSyncImpl(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    AANoSyncImpl::initialize(A);
    Function *F = getAssociatedFunction();
    if (!F || F->isDeclaration())
      indicatePessimisticFixpoint();
  }
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    // TODO: Once we have call site specific value information we can provide
    //       call site specific liveness information and then it makes
    //       sense to specialize attributes for call sites arguments instead of
    //       redirecting requests to the callee argument.
    Function *F = getAssociatedFunction();
    const IRPosition &FnPos = IRPosition::function(*F);
    auto &FnAA = A.getAAFor<AANoSync>(*this, FnPos, DepClassTy::REQUIRED);
    return clampStateAndIndicateChange(getState(), FnAA.getState());
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(nosync); }
};
} // namespace
 
/// ------------------------ No-Free Attributes ----------------------------
 
namespace {
struct AANoFreeImpl : public AANoFree {
  AANoFreeImpl(const IRPosition &IRP, Attributor &A) : AANoFree(IRP, A) {}
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    auto CheckForNoFree = [&](Instruction &I) {
      const auto &CB = cast<CallBase>(I);
      if (CB.hasFnAttr(Attribute::NoFree))
        return true;
 
      const auto &NoFreeAA = A.getAAFor<AANoFree>(
          *this, IRPosition::callsite_function(CB), DepClassTy::REQUIRED);
      return NoFreeAA.isAssumedNoFree();
    };
 
    bool UsedAssumedInformation = false;
    if (!A.checkForAllCallLikeInstructions(CheckForNoFree, *this,
                                           UsedAssumedInformation))
      return indicatePessimisticFixpoint();
    return ChangeStatus::UNCHANGED;
  }
 
  /// See AbstractAttribute::getAsStr().
  const std::string getAsStr() const override {
    return getAssumed() ? "nofree" : "may-free";
  }
};
 
struct AANoFreeFunction final : public AANoFreeImpl {
  AANoFreeFunction(const IRPosition &IRP, Attributor &A)
      : AANoFreeImpl(IRP, A) {}
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(nofree) }
};
 
/// NoFree attribute deduction for a call sites.
struct AANoFreeCallSite final : AANoFreeImpl {
  AANoFreeCallSite(const IRPosition &IRP, Attributor &A)
      : AANoFreeImpl(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    AANoFreeImpl::initialize(A);
    Function *F = getAssociatedFunction();
    if (!F || F->isDeclaration())
      indicatePessimisticFixpoint();
  }
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    // TODO: Once we have call site specific value information we can provide
    //       call site specific liveness information and then it makes
    //       sense to specialize attributes for call sites arguments instead of
    //       redirecting requests to the callee argument.
    Function *F = getAssociatedFunction();
    const IRPosition &FnPos = IRPosition::function(*F);
    auto &FnAA = A.getAAFor<AANoFree>(*this, FnPos, DepClassTy::REQUIRED);
    return clampStateAndIndicateChange(getState(), FnAA.getState());
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(nofree); }
};
 
/// NoFree attribute for floating values.
struct AANoFreeFloating : AANoFreeImpl {
  AANoFreeFloating(const IRPosition &IRP, Attributor &A)
      : AANoFreeImpl(IRP, A) {}
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override{STATS_DECLTRACK_FLOATING_ATTR(nofree)}
 
  /// See Abstract Attribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    const IRPosition &IRP = getIRPosition();
 
    const auto &NoFreeAA = A.getAAFor<AANoFree>(
        *this, IRPosition::function_scope(IRP), DepClassTy::OPTIONAL);
    if (NoFreeAA.isAssumedNoFree())
      return ChangeStatus::UNCHANGED;
 
    Value &AssociatedValue = getIRPosition().getAssociatedValue();
    auto Pred = [&](const Use &U, bool &Follow) -> bool {
      Instruction *UserI = cast<Instruction>(U.getUser());
      if (auto *CB = dyn_cast<CallBase>(UserI)) {
        if (CB->isBundleOperand(&U))
          return false;
        if (!CB->isArgOperand(&U))
          return true;
        unsigned ArgNo = CB->getArgOperandNo(&U);
 
        const auto &NoFreeArg = A.getAAFor<AANoFree>(
            *this, IRPosition::callsite_argument(*CB, ArgNo),
            DepClassTy::REQUIRED);
        return NoFreeArg.isAssumedNoFree();
      }
 
      if (isa<GetElementPtrInst>(UserI) || isa<BitCastInst>(UserI) ||
          isa<PHINode>(UserI) || isa<SelectInst>(UserI)) {
        Follow = true;
        return true;
      }
      if (isa<StoreInst>(UserI) || isa<LoadInst>(UserI) ||
          isa<ReturnInst>(UserI))
        return true;
 
      // Unknown user.
      return false;
    };
    if (!A.checkForAllUses(Pred, *this, AssociatedValue))
      return indicatePessimisticFixpoint();
 
    return ChangeStatus::UNCHANGED;
  }
};
 
/// NoFree attribute for a call site argument.
struct AANoFreeArgument final : AANoFreeFloating {
  AANoFreeArgument(const IRPosition &IRP, Attributor &A)
      : AANoFreeFloating(IRP, A) {}
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(nofree) }
};
 
/// NoFree attribute for call site arguments.
struct AANoFreeCallSiteArgument final : AANoFreeFloating {
  AANoFreeCallSiteArgument(const IRPosition &IRP, Attributor &A)
      : AANoFreeFloating(IRP, A) {}
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    // TODO: Once we have call site specific value information we can provide
    //       call site specific liveness information and then it makes
    //       sense to specialize attributes for call sites arguments instead of
    //       redirecting requests to the callee argument.
    Argument *Arg = getAssociatedArgument();
    if (!Arg)
      return indicatePessimisticFixpoint();
    const IRPosition &ArgPos = IRPosition::argument(*Arg);
    auto &ArgAA = A.getAAFor<AANoFree>(*this, ArgPos, DepClassTy::REQUIRED);
    return clampStateAndIndicateChange(getState(), ArgAA.getState());
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override{STATS_DECLTRACK_CSARG_ATTR(nofree)};
};
 
/// NoFree attribute for function return value.
struct AANoFreeReturned final : AANoFreeFloating {
  AANoFreeReturned(const IRPosition &IRP, Attributor &A)
      : AANoFreeFloating(IRP, A) {
    llvm_unreachable("NoFree is not applicable to function returns!");
  }
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    llvm_unreachable("NoFree is not applicable to function returns!");
  }
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    llvm_unreachable("NoFree is not applicable to function returns!");
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override {}
};
 
/// NoFree attribute deduction for a call site return value.
struct AANoFreeCallSiteReturned final : AANoFreeFloating {
  AANoFreeCallSiteReturned(const IRPosition &IRP, Attributor &A)
      : AANoFreeFloating(IRP, A) {}
 
  ChangeStatus manifest(Attributor &A) override {
    return ChangeStatus::UNCHANGED;
  }
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(nofree) }
};
} // namespace
 
/// ------------------------ NonNull Argument Attribute ------------------------
namespace {
static int64_t getKnownNonNullAndDerefBytesForUse(
    Attributor &A, const AbstractAttribute &QueryingAA, Value &AssociatedValue,
    const Use *U, const Instruction *I, bool &IsNonNull, bool &TrackUse) {
  TrackUse = false;
 
  const Value *UseV = U->get();
  if (!UseV->getType()->isPointerTy())
    return 0;
 
  // We need to follow common pointer manipulation uses to the accesses they
  // feed into. We can try to be smart to avoid looking through things we do not
  // like for now, e.g., non-inbounds GEPs.
  if (isa<CastInst>(I)) {
    TrackUse = true;
    return 0;
  }
 
  if (isa<GetElementPtrInst>(I)) {
    TrackUse = true;
    return 0;
  }
 
  Type *PtrTy = UseV->getType();
  const Function *F = I->getFunction();
  bool NullPointerIsDefined =
      F ? llvm::NullPointerIsDefined(F, PtrTy->getPointerAddressSpace()) : true;
  const DataLayout &DL = A.getInfoCache().getDL();
  if (const auto *CB = dyn_cast<CallBase>(I)) {
    if (CB->isBundleOperand(U)) {
      if (RetainedKnowledge RK = getKnowledgeFromUse(
              U, {Attribute::NonNull, Attribute::Dereferenceable})) {
        IsNonNull |=
            (RK.AttrKind == Attribute::NonNull || !NullPointerIsDefined);
        return RK.ArgValue;
      }
      return 0;
    }
 
    if (CB->isCallee(U)) {
      IsNonNull |= !NullPointerIsDefined;
      return 0;
    }
 
    unsigned ArgNo = CB->getArgOperandNo(U);
    IRPosition IRP = IRPosition::callsite_argument(*CB, ArgNo);
    // As long as we only use known information there is no need to track
    // dependences here.
    auto &DerefAA =
        A.getAAFor<AADereferenceable>(QueryingAA, IRP, DepClassTy::NONE);
    IsNonNull |= DerefAA.isKnownNonNull();
    return DerefAA.getKnownDereferenceableBytes();
  }
 
  Optional<MemoryLocation> Loc = MemoryLocation::getOrNone(I);
  if (!Loc || Loc->Ptr != UseV || !Loc->Size.isPrecise() || I->isVolatile())
    return 0;
 
  int64_t Offset;
  const Value *Base =
      getMinimalBaseOfPointer(A, QueryingAA, Loc->Ptr, Offset, DL);
  if (Base && Base == &AssociatedValue) {
    int64_t DerefBytes = Loc->Size.getValue() + Offset;
    IsNonNull |= !NullPointerIsDefined;
    return std::max(int64_t(0), DerefBytes);
  }
 
  /// Corner case when an offset is 0.
  Base = GetPointerBaseWithConstantOffset(Loc->Ptr, Offset, DL,
                                          /*AllowNonInbounds*/ true);
  if (Base && Base == &AssociatedValue && Offset == 0) {
    int64_t DerefBytes = Loc->Size.getValue();
    IsNonNull |= !NullPointerIsDefined;
    return std::max(int64_t(0), DerefBytes);
  }
 
  return 0;
}
 
struct AANonNullImpl : AANonNull {
  AANonNullImpl(const IRPosition &IRP, Attributor &A)
      : AANonNull(IRP, A),
        NullIsDefined(NullPointerIsDefined(
            getAnchorScope(),
            getAssociatedValue().getType()->getPointerAddressSpace())) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    Value &V = getAssociatedValue();
    if (!NullIsDefined &&
        hasAttr({Attribute::NonNull, Attribute::Dereferenceable},
                /* IgnoreSubsumingPositions */ false, &A)) {
      indicateOptimisticFixpoint();
      return;
    }
 
    if (isa<ConstantPointerNull>(V)) {
      indicatePessimisticFixpoint();
      return;
    }
 
    AANonNull::initialize(A);
 
    bool CanBeNull, CanBeFreed;
    if (V.getPointerDereferenceableBytes(A.getDataLayout(), CanBeNull,
                                         CanBeFreed)) {
      if (!CanBeNull) {
        indicateOptimisticFixpoint();
        return;
      }
    }
 
    if (isa<GlobalValue>(&getAssociatedValue())) {
      indicatePessimisticFixpoint();
      return;
    }
 
    if (Instruction *CtxI = getCtxI())
      followUsesInMBEC(*this, A, getState(), *CtxI);
  }
 
  /// See followUsesInMBEC
  bool followUseInMBEC(Attributor &A, const Use *U, const Instruction *I,
                       AANonNull::StateType &State) {
    bool IsNonNull = false;
    bool TrackUse = false;
    getKnownNonNullAndDerefBytesForUse(A, *this, getAssociatedValue(), U, I,
                                       IsNonNull, TrackUse);
    State.setKnown(IsNonNull);
    return TrackUse;
  }
 
  /// See AbstractAttribute::getAsStr().
  const std::string getAsStr() const override {
    return getAssumed() ? "nonnull" : "may-null";
  }
 
  /// Flag to determine if the underlying value can be null and still allow
  /// valid accesses.
  const bool NullIsDefined;
};
 
/// NonNull attribute for a floating value.
struct AANonNullFloating : public AANonNullImpl {
  AANonNullFloating(const IRPosition &IRP, Attributor &A)
      : AANonNullImpl(IRP, A) {}
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    const DataLayout &DL = A.getDataLayout();
 
    DominatorTree *DT = nullptr;
    AssumptionCache *AC = nullptr;
    InformationCache &InfoCache = A.getInfoCache();
    if (const Function *Fn = getAnchorScope()) {
      DT = InfoCache.getAnalysisResultForFunction<DominatorTreeAnalysis>(*Fn);
      AC = InfoCache.getAnalysisResultForFunction<AssumptionAnalysis>(*Fn);
    }
 
    auto VisitValueCB = [&](Value &V, const Instruction *CtxI,
                            AANonNull::StateType &T, bool Stripped) -> bool {
      const auto &AA = A.getAAFor<AANonNull>(*this, IRPosition::value(V),
                                             DepClassTy::REQUIRED);
      if (!Stripped && this == &AA) {
        if (!isKnownNonZero(&V, DL, 0, AC, CtxI, DT))
          T.indicatePessimisticFixpoint();
      } else {
        // Use abstract attribute information.
        const AANonNull::StateType &NS = AA.getState();
        T ^= NS;
      }
      return T.isValidState();
    };
 
    StateType T;
    bool UsedAssumedInformation = false;
    if (!genericValueTraversal<StateType>(A, getIRPosition(), *this, T,
                                          VisitValueCB, getCtxI(),
                                          UsedAssumedInformation))
      return indicatePessimisticFixpoint();
 
    return clampStateAndIndicateChange(getState(), T);
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(nonnull) }
};
 
/// NonNull attribute for function return value.
struct AANonNullReturned final
    : AAReturnedFromReturnedValues<AANonNull, AANonNull> {
  AANonNullReturned(const IRPosition &IRP, Attributor &A)
      : AAReturnedFromReturnedValues<AANonNull, AANonNull>(IRP, A) {}
 
  /// See AbstractAttribute::getAsStr().
  const std::string getAsStr() const override {
    return getAssumed() ? "nonnull" : "may-null";
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(nonnull) }
};
 
/// NonNull attribute for function argument.
struct AANonNullArgument final
    : AAArgumentFromCallSiteArguments<AANonNull, AANonNullImpl> {
  AANonNullArgument(const IRPosition &IRP, Attributor &A)
      : AAArgumentFromCallSiteArguments<AANonNull, AANonNullImpl>(IRP, A) {}
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(nonnull) }
};
 
struct AANonNullCallSiteArgument final : AANonNullFloating {
  AANonNullCallSiteArgument(const IRPosition &IRP, Attributor &A)
      : AANonNullFloating(IRP, A) {}
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(nonnull) }
};
 
/// NonNull attribute for a call site return position.
struct AANonNullCallSiteReturned final
    : AACallSiteReturnedFromReturned<AANonNull, AANonNullImpl> {
  AANonNullCallSiteReturned(const IRPosition &IRP, Attributor &A)
      : AACallSiteReturnedFromReturned<AANonNull, AANonNullImpl>(IRP, A) {}
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(nonnull) }
};
} // namespace
 
/// ------------------------ No-Recurse Attributes ----------------------------
 
namespace {
struct AANoRecurseImpl : public AANoRecurse {
  AANoRecurseImpl(const IRPosition &IRP, Attributor &A) : AANoRecurse(IRP, A) {}
 
  /// See AbstractAttribute::getAsStr()
  const std::string getAsStr() const override {
    return getAssumed() ? "norecurse" : "may-recurse";
  }
};
 
struct AANoRecurseFunction final : AANoRecurseImpl {
  AANoRecurseFunction(const IRPosition &IRP, Attributor &A)
      : AANoRecurseImpl(IRP, A) {}
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
 
    // If all live call sites are known to be no-recurse, we are as well.
    auto CallSitePred = [&](AbstractCallSite ACS) {
      const auto &NoRecurseAA = A.getAAFor<AANoRecurse>(
          *this, IRPosition::function(*ACS.getInstruction()->getFunction()),
          DepClassTy::NONE);
      return NoRecurseAA.isKnownNoRecurse();
    };
    bool UsedAssumedInformation = false;
    if (A.checkForAllCallSites(CallSitePred, *this, true,
                               UsedAssumedInformation)) {
      // If we know all call sites and all are known no-recurse, we are done.
      // If all known call sites, which might not be all that exist, are known
      // to be no-recurse, we are not done but we can continue to assume
      // no-recurse. If one of the call sites we have not visited will become
      // live, another update is triggered.
      if (!UsedAssumedInformation)
        indicateOptimisticFixpoint();
      return ChangeStatus::UNCHANGED;
    }
 
    const AAFunctionReachability &EdgeReachability =
        A.getAAFor<AAFunctionReachability>(*this, getIRPosition(),
                                           DepClassTy::REQUIRED);
    if (EdgeReachability.canReach(A, *getAnchorScope()))
      return indicatePessimisticFixpoint();
    return ChangeStatus::UNCHANGED;
  }
 
  void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(norecurse) }
};
 
/// NoRecurse attribute deduction for a call sites.
struct AANoRecurseCallSite final : AANoRecurseImpl {
  AANoRecurseCallSite(const IRPosition &IRP, Attributor &A)
      : AANoRecurseImpl(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    AANoRecurseImpl::initialize(A);
    Function *F = getAssociatedFunction();
    if (!F || F->isDeclaration())
      indicatePessimisticFixpoint();
  }
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    // TODO: Once we have call site specific value information we can provide
    //       call site specific liveness information and then it makes
    //       sense to specialize attributes for call sites arguments instead of
    //       redirecting requests to the callee argument.
    Function *F = getAssociatedFunction();
    const IRPosition &FnPos = IRPosition::function(*F);
    auto &FnAA = A.getAAFor<AANoRecurse>(*this, FnPos, DepClassTy::REQUIRED);
    return clampStateAndIndicateChange(getState(), FnAA.getState());
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(norecurse); }
};
} // namespace
 
/// -------------------- Undefined-Behavior Attributes ------------------------
 
namespace {
struct AAUndefinedBehaviorImpl : public AAUndefinedBehavior {
  AAUndefinedBehaviorImpl(const IRPosition &IRP, Attributor &A)
      : AAUndefinedBehavior(IRP, A) {}
 
  /// See AbstractAttribute::updateImpl(...).
  // through a pointer (i.e. also branches etc.)
  ChangeStatus updateImpl(Attributor &A) override {
    const size_t UBPrevSize = KnownUBInsts.size();
    const size_t NoUBPrevSize = AssumedNoUBInsts.size();
 
    auto InspectMemAccessInstForUB = [&](Instruction &I) {
      // Lang ref now states volatile store is not UB, let's skip them.
      if (I.isVolatile() && I.mayWriteToMemory())
        return true;
 
      // Skip instructions that are already saved.
      if (AssumedNoUBInsts.count(&I) || KnownUBInsts.count(&I))
        return true;
 
      // If we reach here, we know we have an instruction
      // that accesses memory through a pointer operand,
      // for which getPointerOperand() should give it to us.
      Value *PtrOp =
          const_cast<Value *>(getPointerOperand(&I, /* AllowVolatile */ true));
      assert(PtrOp &&
             "Expected pointer operand of memory accessing instruction");
 
      // Either we stopped and the appropriate action was taken,
      // or we got back a simplified value to continue.
      Optional<Value *> SimplifiedPtrOp = stopOnUndefOrAssumed(A, PtrOp, &I);
      if (!SimplifiedPtrOp.hasValue() || !SimplifiedPtrOp.getValue())
        return true;
      const Value *PtrOpVal = SimplifiedPtrOp.getValue();
 
      // A memory access through a pointer is considered UB
      // only if the pointer has constant null value.
      // TODO: Expand it to not only check constant values.
      if (!isa<ConstantPointerNull>(PtrOpVal)) {
        AssumedNoUBInsts.insert(&I);
        return true;
      }
      const Type *PtrTy = PtrOpVal->getType();
 
      // Because we only consider instructions inside functions,
      // assume that a parent function exists.
      const Function *F = I.getFunction();
 
      // A memory access using constant null pointer is only considered UB
      // if null pointer is _not_ defined for the target platform.
      if (llvm::NullPointerIsDefined(F, PtrTy->getPointerAddressSpace()))
        AssumedNoUBInsts.insert(&I);
      else
        KnownUBInsts.insert(&I);
      return true;
    };
 
    auto InspectBrInstForUB = [&](Instruction &I) {
      // A conditional branch instruction is considered UB if it has `undef`
      // condition.
 
      // Skip instructions that are already saved.
      if (AssumedNoUBInsts.count(&I) || KnownUBInsts.count(&I))
        return true;
 
      // We know we have a branch instruction.
      auto *BrInst = cast<BranchInst>(&I);
 
      // Unconditional branches are never considered UB.
      if (BrInst->isUnconditional())
        return true;
 
      // Either we stopped and the appropriate action was taken,
      // or we got back a simplified value to continue.
      Optional<Value *> SimplifiedCond =
          stopOnUndefOrAssumed(A, BrInst->getCondition(), BrInst);
      if (!SimplifiedCond.hasValue() || !SimplifiedCond.getValue())
        return true;
      AssumedNoUBInsts.insert(&I);
      return true;
    };
 
    auto InspectCallSiteForUB = [&](Instruction &I) {
      // Check whether a callsite always cause UB or not
 
      // Skip instructions that are already saved.
      if (AssumedNoUBInsts.count(&I) || KnownUBInsts.count(&I))
        return true;
 
      // Check nonnull and noundef argument attribute violation for each
      // callsite.
      CallBase &CB = cast<CallBase>(I);
      Function *Callee = CB.getCalledFunction();
      if (!Callee)
        return true;
      for (unsigned idx = 0; idx < CB.arg_size(); idx++) {
        // If current argument is known to be simplified to null pointer and the
        // corresponding argument position is known to have nonnull attribute,
        // the argument is poison. Furthermore, if the argument is poison and
        // the position is known to have noundef attriubte, this callsite is
        // considered UB.
        if (idx >= Callee->arg_size())
          break;
        Value *ArgVal = CB.getArgOperand(idx);
        if (!ArgVal)
          continue;
        // Here, we handle three cases.
        //   (1) Not having a value means it is dead. (we can replace the value
        //       with undef)
        //   (2) Simplified to undef. The argument violate noundef attriubte.
        //   (3) Simplified to null pointer where known to be nonnull.
        //       The argument is a poison value and violate noundef attribute.
        IRPosition CalleeArgumentIRP = IRPosition::callsite_argument(CB, idx);
        auto &NoUndefAA =
            A.getAAFor<AANoUndef>(*this, CalleeArgumentIRP, DepClassTy::NONE);
        if (!NoUndefAA.isKnownNoUndef())
          continue;
        bool UsedAssumedInformation = false;
        Optional<Value *> SimplifiedVal = A.getAssumedSimplified(
            IRPosition::value(*ArgVal), *this, UsedAssumedInformation);
        if (UsedAssumedInformation)
          continue;
        if (SimplifiedVal.hasValue() && !SimplifiedVal.getValue())
          return true;
        if (!SimplifiedVal.hasValue() ||
            isa<UndefValue>(*SimplifiedVal.getValue())) {
          KnownUBInsts.insert(&I);
          continue;
        }
        if (!ArgVal->getType()->isPointerTy() ||
            !isa<ConstantPointerNull>(*SimplifiedVal.getValue()))
          continue;
        auto &NonNullAA =
            A.getAAFor<AANonNull>(*this, CalleeArgumentIRP, DepClassTy::NONE);
        if (NonNullAA.isKnownNonNull())
          KnownUBInsts.insert(&I);
      }
      return true;
    };
 
    auto InspectReturnInstForUB = [&](Instruction &I) {
      auto &RI = cast<ReturnInst>(I);
      // Either we stopped and the appropriate action was taken,
      // or we got back a simplified return value to continue.
      Optional<Value *> SimplifiedRetValue =
          stopOnUndefOrAssumed(A, RI.getReturnValue(), &I);
      if (!SimplifiedRetValue.hasValue() || !SimplifiedRetValue.getValue())
        return true;
 
      // Check if a return instruction always cause UB or not
      // Note: It is guaranteed that the returned position of the anchor
      //       scope has noundef attribute when this is called.
      //       We also ensure the return position is not "assumed dead"
      //       because the returned value was then potentially simplified to
      //       `undef` in AAReturnedValues without removing the `noundef`
      //       attribute yet.
 
      // When the returned position has noundef attriubte, UB occurs in the
      // following cases.
      //   (1) Returned value is known to be undef.
      //   (2) The value is known to be a null pointer and the returned
      //       position has nonnull attribute (because the returned value is
      //       poison).
      if (isa<ConstantPointerNull>(*SimplifiedRetValue)) {
        auto &NonNullAA = A.getAAFor<AANonNull>(
            *this, IRPosition::returned(*getAnchorScope()), DepClassTy::NONE);
        if (NonNullAA.isKnownNonNull())
          KnownUBInsts.insert(&I);
      }
 
      return true;
    };
 
    bool UsedAssumedInformation = false;
    A.checkForAllInstructions(InspectMemAccessInstForUB, *this,
                              {Instruction::Load, Instruction::Store,
                               Instruction::AtomicCmpXchg,
                               Instruction::AtomicRMW},
                              UsedAssumedInformation,
                              /* CheckBBLivenessOnly */ true);
    A.checkForAllInstructions(InspectBrInstForUB, *this, {Instruction::Br},
                              UsedAssumedInformation,
                              /* CheckBBLivenessOnly */ true);
    A.checkForAllCallLikeInstructions(InspectCallSiteForUB, *this,
                                      UsedAssumedInformation);
 
    // If the returned position of the anchor scope has noundef attriubte, check
    // all returned instructions.
    if (!getAnchorScope()->getReturnType()->isVoidTy()) {
      const IRPosition &ReturnIRP = IRPosition::returned(*getAnchorScope());
      if (!A.isAssumedDead(ReturnIRP, this, nullptr, UsedAssumedInformation)) {
        auto &RetPosNoUndefAA =
            A.getAAFor<AANoUndef>(*this, ReturnIRP, DepClassTy::NONE);
        if (RetPosNoUndefAA.isKnownNoUndef())
          A.checkForAllInstructions(InspectReturnInstForUB, *this,
                                    {Instruction::Ret}, UsedAssumedInformation,
                                    /* CheckBBLivenessOnly */ true);
      }
    }
 
    if (NoUBPrevSize != AssumedNoUBInsts.size() ||
        UBPrevSize != KnownUBInsts.size())
      return ChangeStatus::CHANGED;
    return ChangeStatus::UNCHANGED;
  }
 
  bool isKnownToCauseUB(Instruction *I) const override {
    return KnownUBInsts.count(I);
  }
 
  bool isAssumedToCauseUB(Instruction *I) const override {
    // In simple words, if an instruction is not in the assumed to _not_
    // cause UB, then it is assumed UB (that includes those
    // in the KnownUBInsts set). The rest is boilerplate
    // is to ensure that it is one of the instructions we test
    // for UB.
 
    switch (I->getOpcode()) {
    case Instruction::Load:
    case Instruction::Store:
    case Instruction::AtomicCmpXchg:
    case Instruction::AtomicRMW:
      return !AssumedNoUBInsts.count(I);
    case Instruction::Br: {
      auto *BrInst = cast<BranchInst>(I);
      if (BrInst->isUnconditional())
        return false;
      return !AssumedNoUBInsts.count(I);
    } break;
    default:
      return false;
    }
    return false;
  }
 
  ChangeStatus manifest(Attributor &A) override {
    if (KnownUBInsts.empty())
      return ChangeStatus::UNCHANGED;
    for (Instruction *I : KnownUBInsts)
      A.changeToUnreachableAfterManifest(I);
    return ChangeStatus::CHANGED;
  }
 
  /// See AbstractAttribute::getAsStr()
  const std::string getAsStr() const override {
    return getAssumed() ? "undefined-behavior" : "no-ub";
  }
 
  /// Note: The correctness of this analysis depends on the fact that the
  /// following 2 sets will stop changing after some point.
  /// "Change" here means that their size changes.
  /// The size of each set is monotonically increasing
  /// (we only add items to them) and it is upper bounded by the number of
  /// instructions in the processed function (we can never save more
  /// elements in either set than this number). Hence, at some point,
  /// they will stop increasing.
  /// Consequently, at some point, both sets will have stopped
  /// changing, effectively making the analysis reach a fixpoint.
 
  /// Note: These 2 sets are disjoint and an instruction can be considered
  /// one of 3 things:
  /// 1) Known to cause UB (AAUndefinedBehavior could prove it) and put it in
  ///    the KnownUBInsts set.
  /// 2) Assumed to cause UB (in every updateImpl, AAUndefinedBehavior
  ///    has a reason to assume it).
  /// 3) Assumed to not cause UB. very other instruction - AAUndefinedBehavior
  ///    could not find a reason to assume or prove that it can cause UB,
  ///    hence it assumes it doesn't. We have a set for these instructions
  ///    so that we don't reprocess them in every update.
  ///    Note however that instructions in this set may cause UB.
 
protected:
  /// A set of all live instructions _known_ to cause UB.
  SmallPtrSet<Instruction *, 8> KnownUBInsts;
 
private:
  /// A set of all the (live) instructions that are assumed to _not_ cause UB.
  SmallPtrSet<Instruction *, 8> AssumedNoUBInsts;
 
  // Should be called on updates in which if we're processing an instruction
  // \p I that depends on a value \p V, one of the following has to happen:
  // - If the value is assumed, then stop.
  // - If the value is known but undef, then consider it UB.
  // - Otherwise, do specific processing with the simplified value.
  // We return None in the first 2 cases to signify that an appropriate
  // action was taken and the caller should stop.
  // Otherwise, we return the simplified value that the caller should
  // use for specific processing.
  Optional<Value *> stopOnUndefOrAssumed(Attributor &A, Value *V,
                                         Instruction *I) {
    bool UsedAssumedInformation = false;
    Optional<Value *> SimplifiedV = A.getAssumedSimplified(
        IRPosition::value(*V), *this, UsedAssumedInformation);
    if (!UsedAssumedInformation) {
      // Don't depend on assumed values.
      if (!SimplifiedV.hasValue()) {
        // If it is known (which we tested above) but it doesn't have a value,
        // then we can assume `undef` and hence the instruction is UB.
        KnownUBInsts.insert(I);
        return llvm::None;
      }
      if (!SimplifiedV.getValue())
        return nullptr;
      V = *SimplifiedV;
    }
    if (isa<UndefValue>(V)) {
      KnownUBInsts.insert(I);
      return llvm::None;
    }
    return V;
  }
};
 
struct AAUndefinedBehaviorFunction final : AAUndefinedBehaviorImpl {
  AAUndefinedBehaviorFunction(const IRPosition &IRP, Attributor &A)
      : AAUndefinedBehaviorImpl(IRP, A) {}
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override {
    STATS_DECL(UndefinedBehaviorInstruction, Instruction,
               "Number of instructions known to have UB");
    BUILD_STAT_NAME(UndefinedBehaviorInstruction, Instruction) +=
        KnownUBInsts.size();
  }
};
} // namespace
 
/// ------------------------ Will-Return Attributes ----------------------------
 
namespace {
// Helper function that checks whether a function has any cycle which we don't
// know if it is bounded or not.
// Loops with maximum trip count are considered bounded, any other cycle not.
static bool mayContainUnboundedCycle(Function &F, Attributor &A) {
  ScalarEvolution *SE =
      A.getInfoCache().getAnalysisResultForFunction<ScalarEvolutionAnalysis>(F);
  LoopInfo *LI = A.getInfoCache().getAnalysisResultForFunction<LoopAnalysis>(F);
  // If either SCEV or LoopInfo is not available for the function then we assume
  // any cycle to be unbounded cycle.
  // We use scc_iterator which uses Tarjan algorithm to find all the maximal
  // SCCs.To detect if there's a cycle, we only need to find the maximal ones.
  if (!SE || !LI) {
    for (scc_iterator<Function *> SCCI = scc_begin(&F); !SCCI.isAtEnd(); ++SCCI)
      if (SCCI.hasCycle())
        return true;
    return false;
  }
 
  // If there's irreducible control, the function may contain non-loop cycles.
  if (mayContainIrreducibleControl(F, LI))
    return true;
 
  // Any loop that does not have a max trip count is considered unbounded cycle.
  for (auto *L : LI->getLoopsInPreorder()) {
    if (!SE->getSmallConstantMaxTripCount(L))
      return true;
  }
  return false;
}
 
struct AAWillReturnImpl : public AAWillReturn {
  AAWillReturnImpl(const IRPosition &IRP, Attributor &A)
      : AAWillReturn(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    AAWillReturn::initialize(A);
 
    if (isImpliedByMustprogressAndReadonly(A, /* KnownOnly */ true)) {
      indicateOptimisticFixpoint();
      return;
    }
  }
 
  /// Check for `mustprogress` and `readonly` as they imply `willreturn`.
  bool isImpliedByMustprogressAndReadonly(Attributor &A, bool KnownOnly) {
    // Check for `mustprogress` in the scope and the associated function which
    // might be different if this is a call site.
    if ((!getAnchorScope() || !getAnchorScope()->mustProgress()) &&
        (!getAssociatedFunction() || !getAssociatedFunction()->mustProgress()))
      return false;
 
    bool IsKnown;
    if (AA::isAssumedReadOnly(A, getIRPosition(), *this, IsKnown))
      return IsKnown || !KnownOnly;
    return false;
  }
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    if (isImpliedByMustprogressAndReadonly(A, /* KnownOnly */ false))
      return ChangeStatus::UNCHANGED;
 
    auto CheckForWillReturn = [&](Instruction &I) {
      IRPosition IPos = IRPosition::callsite_function(cast<CallBase>(I));
      const auto &WillReturnAA =
          A.getAAFor<AAWillReturn>(*this, IPos, DepClassTy::REQUIRED);
      if (WillReturnAA.isKnownWillReturn())
        return true;
      if (!WillReturnAA.isAssumedWillReturn())
        return false;
      const auto &NoRecurseAA =
          A.getAAFor<AANoRecurse>(*this, IPos, DepClassTy::REQUIRED);
      return NoRecurseAA.isAssumedNoRecurse();
    };
 
    bool UsedAssumedInformation = false;
    if (!A.checkForAllCallLikeInstructions(CheckForWillReturn, *this,
                                           UsedAssumedInformation))
      return indicatePessimisticFixpoint();
 
    return ChangeStatus::UNCHANGED;
  }
 
  /// See AbstractAttribute::getAsStr()
  const std::string getAsStr() const override {
    return getAssumed() ? "willreturn" : "may-noreturn";
  }
};
 
struct AAWillReturnFunction final : AAWillReturnImpl {
  AAWillReturnFunction(const IRPosition &IRP, Attributor &A)
      : AAWillReturnImpl(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    AAWillReturnImpl::initialize(A);
 
    Function *F = getAnchorScope();
    if (!F || F->isDeclaration() || mayContainUnboundedCycle(*F, A))
      indicatePessimisticFixpoint();
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(willreturn) }
};
 
/// WillReturn attribute deduction for a call sites.
struct AAWillReturnCallSite final : AAWillReturnImpl {
  AAWillReturnCallSite(const IRPosition &IRP, Attributor &A)
      : AAWillReturnImpl(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    AAWillReturnImpl::initialize(A);
    Function *F = getAssociatedFunction();
    if (!F || !A.isFunctionIPOAmendable(*F))
      indicatePessimisticFixpoint();
  }
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    if (isImpliedByMustprogressAndReadonly(A, /* KnownOnly */ false))
      return ChangeStatus::UNCHANGED;
 
    // TODO: Once we have call site specific value information we can provide
    //       call site specific liveness information and then it makes
    //       sense to specialize attributes for call sites arguments instead of
    //       redirecting requests to the callee argument.
    Function *F = getAssociatedFunction();
    const IRPosition &FnPos = IRPosition::function(*F);
    auto &FnAA = A.getAAFor<AAWillReturn>(*this, FnPos, DepClassTy::REQUIRED);
    return clampStateAndIndicateChange(getState(), FnAA.getState());
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(willreturn); }
};
} // namespace
 
/// -------------------AAReachability Attribute--------------------------
 
namespace {
struct AAReachabilityImpl : AAReachability {
  AAReachabilityImpl(const IRPosition &IRP, Attributor &A)
      : AAReachability(IRP, A) {}
 
  const std::string getAsStr() const override {
    // TODO: Return the number of reachable queries.
    return "reachable";
  }
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    return ChangeStatus::UNCHANGED;
  }
};
 
struct AAReachabilityFunction final : public AAReachabilityImpl {
  AAReachabilityFunction(const IRPosition &IRP, Attributor &A)
      : AAReachabilityImpl(IRP, A) {}
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(reachable); }
};
} // namespace
 
/// ------------------------ NoAlias Argument Attribute ------------------------
 
namespace {
struct AANoAliasImpl : AANoAlias {
  AANoAliasImpl(const IRPosition &IRP, Attributor &A) : AANoAlias(IRP, A) {
    assert(getAssociatedType()->isPointerTy() &&
           "Noalias is a pointer attribute");
  }
 
  const std::string getAsStr() const override {
    return getAssumed() ? "noalias" : "may-alias";
  }
};
 
/// NoAlias attribute for a floating value.
struct AANoAliasFloating final : AANoAliasImpl {
  AANoAliasFloating(const IRPosition &IRP, Attributor &A)
      : AANoAliasImpl(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    AANoAliasImpl::initialize(A);
    Value *Val = &getAssociatedValue();
    do {
      CastInst *CI = dyn_cast<CastInst>(Val);
      if (!CI)
        break;
      Value *Base = CI->getOperand(0);
      if (!Base->hasOneUse())
        break;
      Val = Base;
    } while (true);
 
    if (!Val->getType()->isPointerTy()) {
      indicatePessimisticFixpoint();
      return;
    }
 
    if (isa<AllocaInst>(Val))
      indicateOptimisticFixpoint();
    else if (isa<ConstantPointerNull>(Val) &&
             !NullPointerIsDefined(getAnchorScope(),
                                   Val->getType()->getPointerAddressSpace()))
      indicateOptimisticFixpoint();
    else if (Val != &getAssociatedValue()) {
      const auto &ValNoAliasAA = A.getAAFor<AANoAlias>(
          *this, IRPosition::value(*Val), DepClassTy::OPTIONAL);
      if (ValNoAliasAA.isKnownNoAlias())
        indicateOptimisticFixpoint();
    }
  }
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    // TODO: Implement this.
    return indicatePessimisticFixpoint();
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override {
    STATS_DECLTRACK_FLOATING_ATTR(noalias)
  }
};
 
/// NoAlias attribute for an argument.
struct AANoAliasArgument final
    : AAArgumentFromCallSiteArguments<AANoAlias, AANoAliasImpl> {
  using Base = AAArgumentFromCallSiteArguments<AANoAlias, AANoAliasImpl>;
  AANoAliasArgument(const IRPosition &IRP, Attributor &A) : Base(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    Base::initialize(A);
    // See callsite argument attribute and callee argument attribute.
    if (hasAttr({Attribute::ByVal}))
      indicateOptimisticFixpoint();
  }
 
  /// See AbstractAttribute::update(...).
  ChangeStatus updateImpl(Attributor &A) override {
    // We have to make sure no-alias on the argument does not break
    // synchronization when this is a callback argument, see also [1] below.
    // If synchronization cannot be affected, we delegate to the base updateImpl
    // function, otherwise we give up for now.
 
    // If the function is no-sync, no-alias cannot break synchronization.
    const auto &NoSyncAA =
        A.getAAFor<AANoSync>(*this, IRPosition::function_scope(getIRPosition()),
                             DepClassTy::OPTIONAL);
    if (NoSyncAA.isAssumedNoSync())
      return Base::updateImpl(A);
 
    // If the argument is read-only, no-alias cannot break synchronization.
    bool IsKnown;
    if (AA::isAssumedReadOnly(A, getIRPosition(), *this, IsKnown))
      return Base::updateImpl(A);
 
    // If the argument is never passed through callbacks, no-alias cannot break
    // synchronization.
    bool UsedAssumedInformation = false;
    if (A.checkForAllCallSites(
            [](AbstractCallSite ACS) { return !ACS.isCallbackCall(); }, *this,
            true, UsedAssumedInformation))
      return Base::updateImpl(A);
 
    // TODO: add no-alias but make sure it doesn't break synchronization by
    // introducing fake uses. See:
    // [1] Compiler Optimizations for OpenMP, J. Doerfert and H. Finkel,
    //     International Workshop on OpenMP 2018,
    //     http://compilers.cs.uni-saarland.de/people/doerfert/par_opt18.pdf
 
    return indicatePessimisticFixpoint();
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(noalias) }
};
 
struct AANoAliasCallSiteArgument final : AANoAliasImpl {
  AANoAliasCallSiteArgument(const IRPosition &IRP, Attributor &A)
      : AANoAliasImpl(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    // See callsite argument attribute and callee argument attribute.
    const auto &CB = cast<CallBase>(getAnchorValue());
    if (CB.paramHasAttr(getCallSiteArgNo(), Attribute::NoAlias))
      indicateOptimisticFixpoint();
    Value &Val = getAssociatedValue();
    if (isa<ConstantPointerNull>(Val) &&
        !NullPointerIsDefined(getAnchorScope(),
                              Val.getType()->getPointerAddressSpace()))
      indicateOptimisticFixpoint();
  }
 
  /// Determine if the underlying value may alias with the call site argument
  /// \p OtherArgNo of \p ICS (= the underlying call site).
  bool mayAliasWithArgument(Attributor &A, AAResults *&AAR,
                            const AAMemoryBehavior &MemBehaviorAA,
                            const CallBase &CB, unsigned OtherArgNo) {
    // We do not need to worry about aliasing with the underlying IRP.
    if (this->getCalleeArgNo() == (int)OtherArgNo)
      return false;
 
    // If it is not a pointer or pointer vector we do not alias.
    const Value *ArgOp = CB.getArgOperand(OtherArgNo);
    if (!ArgOp->getType()->isPtrOrPtrVectorTy())
      return false;
 
    auto &CBArgMemBehaviorAA = A.getAAFor<AAMemoryBehavior>(
        *this, IRPosition::callsite_argument(CB, OtherArgNo), DepClassTy::NONE);
 
    // If the argument is readnone, there is no read-write aliasing.
    if (CBArgMemBehaviorAA.isAssumedReadNone()) {
      A.recordDependence(CBArgMemBehaviorAA, *this, DepClassTy::OPTIONAL);
      return false;
    }
 
    // If the argument is readonly and the underlying value is readonly, there
    // is no read-write aliasing.
    bool IsReadOnly = MemBehaviorAA.isAssumedReadOnly();
    if (CBArgMemBehaviorAA.isAssumedReadOnly() && IsReadOnly) {
      A.recordDependence(MemBehaviorAA, *this, DepClassTy::OPTIONAL);
      A.recordDependence(CBArgMemBehaviorAA, *this, DepClassTy::OPTIONAL);
      return false;
    }
 
    // We have to utilize actual alias analysis queries so we need the object.
    if (!AAR)
      AAR = A.getInfoCache().getAAResultsForFunction(*getAnchorScope());
 
    // Try to rule it out at the call site.
    bool IsAliasing = !AAR || !AAR->isNoAlias(&getAssociatedValue(), ArgOp);
    LLVM_DEBUG(dbgs() << "[NoAliasCSArg] Check alias between "
                         "callsite arguments: "
                      << getAssociatedValue() << " " << *ArgOp << " => "
                      << (IsAliasing ? "" : "no-") << "alias \n");
 
    return IsAliasing;
  }
 
  bool
  isKnownNoAliasDueToNoAliasPreservation(Attributor &A, AAResults *&AAR,
                                         const AAMemoryBehavior &MemBehaviorAA,
                                         const AANoAlias &NoAliasAA) {
    // We can deduce "noalias" if the following conditions hold.
    // (i)   Associated value is assumed to be noalias in the definition.
    // (ii)  Associated value is assumed to be no-capture in all the uses
    //       possibly executed before this callsite.
    // (iii) There is no other pointer argument which could alias with the
    //       value.
 
    bool AssociatedValueIsNoAliasAtDef = NoAliasAA.isAssumedNoAlias();
    if (!AssociatedValueIsNoAliasAtDef) {
      LLVM_DEBUG(dbgs() << "[AANoAlias] " << getAssociatedValue()
                        << " is not no-alias at the definition\n");
      return false;
    }
 
    auto IsDereferenceableOrNull = [&](Value *O, const DataLayout &DL) {
      const auto &DerefAA = A.getAAFor<AADereferenceable>(
          *this, IRPosition::value(*O), DepClassTy::OPTIONAL);
      return DerefAA.getAssumedDereferenceableBytes();
    };
 
    A.recordDependence(NoAliasAA, *this, DepClassTy::OPTIONAL);
 
    const IRPosition &VIRP = IRPosition::value(getAssociatedValue());
    const Function *ScopeFn = VIRP.getAnchorScope();
    auto &NoCaptureAA = A.getAAFor<AANoCapture>(*this, VIRP, DepClassTy::NONE);
    // Check whether the value is captured in the scope using AANoCapture.
    // Look at CFG and check only uses possibly executed before this
    // callsite.
    auto UsePred = [&](const Use &U, bool &Follow) -> bool {
      Instruction *UserI = cast<Instruction>(U.getUser());
 
      // If UserI is the curr instruction and there is a single potential use of
      // the value in UserI we allow the use.
      // TODO: We should inspect the operands and allow those that cannot alias
      //       with the value.
      if (UserI == getCtxI() && UserI->getNumOperands() == 1)
        return true;
 
      if (ScopeFn) {
        if (auto *CB = dyn_cast<CallBase>(UserI)) {
          if (CB->isArgOperand(&U)) {
 
            unsigned ArgNo = CB->getArgOperandNo(&U);
 
            const auto &NoCaptureAA = A.getAAFor<AANoCapture>(
                *this, IRPosition::callsite_argument(*CB, ArgNo),
                DepClassTy::OPTIONAL);
 
            if (NoCaptureAA.isAssumedNoCapture())
              return true;
          }
        }
 
        if (!AA::isPotentiallyReachable(A, *UserI, *getCtxI(), *this))
          return true;
      }
 
      // TODO: We should track the capturing uses in AANoCapture but the problem
      //       is CGSCC runs. For those we would need to "allow" AANoCapture for
      //       a value in the module slice.
      switch (DetermineUseCaptureKind(U, IsDereferenceableOrNull)) {
      case UseCaptureKind::NO_CAPTURE:
        return true;
      case UseCaptureKind::MAY_CAPTURE:
        LLVM_DEBUG(dbgs() << "[AANoAliasCSArg] Unknown user: " << *UserI
                          << "\n");
        return false;
      case UseCaptureKind::PASSTHROUGH:
        Follow = true;
        return true;
      }
      llvm_unreachable("unknown UseCaptureKind");
    };
 
    if (!NoCaptureAA.isAssumedNoCaptureMaybeReturned()) {
      if (!A.checkForAllUses(UsePred, *this, getAssociatedValue())) {
        LLVM_DEBUG(
            dbgs() << "[AANoAliasCSArg] " << getAssociatedValue()
                   << " cannot be noalias as it is potentially captured\n");
        return false;
      }
    }
    A.recordDependence(NoCaptureAA, *this, DepClassTy::OPTIONAL);
 
    // Check there is no other pointer argument which could alias with the
    // value passed at this call site.
    // TODO: AbstractCallSite
    const auto &CB = cast<CallBase>(getAnchorValue());
    for (unsigned OtherArgNo = 0; OtherArgNo < CB.arg_size(); OtherArgNo++)
      if (mayAliasWithArgument(A, AAR, MemBehaviorAA, CB, OtherArgNo))
        return false;
 
    return true;
  }
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    // If the argument is readnone we are done as there are no accesses via the
    // argument.
    auto &MemBehaviorAA =
        A.getAAFor<AAMemoryBehavior>(*this, getIRPosition(), DepClassTy::NONE);
    if (MemBehaviorAA.isAssumedReadNone()) {
      A.recordDependence(MemBehaviorAA, *this, DepClassTy::OPTIONAL);
      return ChangeStatus::UNCHANGED;
    }
 
    const IRPosition &VIRP = IRPosition::value(getAssociatedValue());
    const auto &NoAliasAA =
        A.getAAFor<AANoAlias>(*this, VIRP, DepClassTy::NONE);
 
    AAResults *AAR = nullptr;
    if (isKnownNoAliasDueToNoAliasPreservation(A, AAR, MemBehaviorAA,
                                               NoAliasAA)) {
      LLVM_DEBUG(
          dbgs() << "[AANoAlias] No-Alias deduced via no-alias preservation\n");
      return ChangeStatus::UNCHANGED;
    }
 
    return indicatePessimisticFixpoint();
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(noalias) }
};
 
/// NoAlias attribute for function return value.
struct AANoAliasReturned final : AANoAliasImpl {
  AANoAliasReturned(const IRPosition &IRP, Attributor &A)
      : AANoAliasImpl(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    AANoAliasImpl::initialize(A);
    Function *F = getAssociatedFunction();
    if (!F || F->isDeclaration())
      indicatePessimisticFixpoint();
  }
 
  /// See AbstractAttribute::updateImpl(...).
  virtual ChangeStatus updateImpl(Attributor &A) override {
 
    auto CheckReturnValue = [&](Value &RV) -> bool {
      if (Constant *C = dyn_cast<Constant>(&RV))
        if (C->isNullValue() || isa<UndefValue>(C))
          return true;
 
      /// For now, we can only deduce noalias if we have call sites.
      /// FIXME: add more support.
      if (!isa<CallBase>(&RV))
        return false;
 
      const IRPosition &RVPos = IRPosition::value(RV);
      const auto &NoAliasAA =
          A.getAAFor<AANoAlias>(*this, RVPos, DepClassTy::REQUIRED);
      if (!NoAliasAA.isAssumedNoAlias())
        return false;
 
      const auto &NoCaptureAA =
          A.getAAFor<AANoCapture>(*this, RVPos, DepClassTy::REQUIRED);
      return NoCaptureAA.isAssumedNoCaptureMaybeReturned();
    };
 
    if (!A.checkForAllReturnedValues(CheckReturnValue, *this))
      return indicatePessimisticFixpoint();
 
    return ChangeStatus::UNCHANGED;
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(noalias) }
};
 
/// NoAlias attribute deduction for a call site return value.
struct AANoAliasCallSiteReturned final : AANoAliasImpl {
  AANoAliasCallSiteReturned(const IRPosition &IRP, Attributor &A)
      : AANoAliasImpl(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    AANoAliasImpl::initialize(A);
    Function *F = getAssociatedFunction();
    if (!F || F->isDeclaration())
      indicatePessimisticFixpoint();
  }
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    // TODO: Once we have call site specific value information we can provide
    //       call site specific liveness information and then it makes
    //       sense to specialize attributes for call sites arguments instead of
    //       redirecting requests to the callee argument.
    Function *F = getAssociatedFunction();
    const IRPosition &FnPos = IRPosition::returned(*F);
    auto &FnAA = A.getAAFor<AANoAlias>(*this, FnPos, DepClassTy::REQUIRED);
    return clampStateAndIndicateChange(getState(), FnAA.getState());
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(noalias); }
};
} // namespace
 
/// -------------------AAIsDead Function Attribute-----------------------
 
namespace {
struct AAIsDeadValueImpl : public AAIsDead {
  AAIsDeadValueImpl(const IRPosition &IRP, Attributor &A) : AAIsDead(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    if (auto *Scope = getAnchorScope())
      if (!A.isRunOn(*Scope))
        indicatePessimisticFixpoint();
  }
 
  /// See AAIsDead::isAssumedDead().
  bool isAssumedDead() const override { return isAssumed(IS_DEAD); }
 
  /// See AAIsDead::isKnownDead().
  bool isKnownDead() const override { return isKnown(IS_DEAD); }
 
  /// See AAIsDead::isAssumedDead(BasicBlock *).
  bool isAssumedDead(const BasicBlock *BB) const override { return false; }
 
  /// See AAIsDead::isKnownDead(BasicBlock *).
  bool isKnownDead(const BasicBlock *BB) const override { return false; }
 
  /// See AAIsDead::isAssumedDead(Instruction *I).
  bool isAssumedDead(const Instruction *I) const override {
    return I == getCtxI() && isAssumedDead();
  }
 
  /// See AAIsDead::isKnownDead(Instruction *I).
  bool isKnownDead(const Instruction *I) const override {
    return isAssumedDead(I) && isKnownDead();
  }
 
  /// See AbstractAttribute::getAsStr().
  virtual const std::string getAsStr() const override {
    return isAssumedDead() ? "assumed-dead" : "assumed-live";
  }
 
  /// Check if all uses are assumed dead.
  bool areAllUsesAssumedDead(Attributor &A, Value &V) {
    // Callers might not check the type, void has no uses.
    if (V.getType()->isVoidTy() || V.use_empty())
      return true;
 
    // If we replace a value with a constant there are no uses left afterwards.
    if (!isa<Constant>(V)) {
      if (auto *I = dyn_cast<Instruction>(&V))
        if (!A.isRunOn(*I->getFunction()))
          return false;
      bool UsedAssumedInformation = false;
      Optional<Constant *> C =
          A.getAssumedConstant(V, *this, UsedAssumedInformation);
      if (!C.hasValue() || *C)
        return true;
    }
 
    auto UsePred = [&](const Use &U, bool &Follow) { return false; };
    // Explicitly set the dependence class to required because we want a long
    // chain of N dependent instructions to be considered live as soon as one is
    // without going through N update cycles. This is not required for
    // correctness.
    return A.checkForAllUses(UsePred, *this, V, /* CheckBBLivenessOnly */ false,
                             DepClassTy::REQUIRED,
                             /* IgnoreDroppableUses */ false);
  }
 
  /// Determine if \p I is assumed to be side-effect free.
  bool isAssumedSideEffectFree(Attributor &A, Instruction *I) {
    if (!I || wouldInstructionBeTriviallyDead(I))
      return true;
 
    auto *CB = dyn_cast<CallBase>(I);
    if (!CB || isa<IntrinsicInst>(CB))
      return false;
 
    const IRPosition &CallIRP = IRPosition::callsite_function(*CB);
    const auto &NoUnwindAA =
        A.getAndUpdateAAFor<AANoUnwind>(*this, CallIRP, DepClassTy::NONE);
    if (!NoUnwindAA.isAssumedNoUnwind())
      return false;
    if (!NoUnwindAA.isKnownNoUnwind())
      A.recordDependence(NoUnwindAA, *this, DepClassTy::OPTIONAL);
 
    bool IsKnown;
    return AA::isAssumedReadOnly(A, CallIRP, *this, IsKnown);
  }
};
 
struct AAIsDeadFloating : public AAIsDeadValueImpl {
  AAIsDeadFloating(const IRPosition &IRP, Attributor &A)
      : AAIsDeadValueImpl(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    AAIsDeadValueImpl::initialize(A);
 
    if (isa<UndefValue>(getAssociatedValue())) {
      indicatePessimisticFixpoint();
      return;
    }
 
    Instruction *I = dyn_cast<Instruction>(&getAssociatedValue());
    if (!isAssumedSideEffectFree(A, I)) {
      if (!isa_and_nonnull<StoreInst>(I))
        indicatePessimisticFixpoint();
      else
        removeAssumedBits(HAS_NO_EFFECT);
    }
  }
 
  bool isDeadStore(Attributor &A, StoreInst &SI) {
    // Lang ref now states volatile store is not UB/dead, let's skip them.
    if (SI.isVolatile())
      return false;
 
    bool UsedAssumedInformation = false;
    SmallSetVector<Value *, 4> PotentialCopies;
    if (!AA::getPotentialCopiesOfStoredValue(A, SI, PotentialCopies, *this,
                                             UsedAssumedInformation))
      return false;
    return llvm::all_of(PotentialCopies, [&](Value *V) {
      return A.isAssumedDead(IRPosition::value(*V), this, nullptr,
                             UsedAssumedInformation);
    });
  }
 
  /// See AbstractAttribute::getAsStr().
  const std::string getAsStr() const override {
    Instruction *I = dyn_cast<Instruction>(&getAssociatedValue());
    if (isa_and_nonnull<StoreInst>(I))
      if (isValidState())
        return "assumed-dead-store";
    return AAIsDeadValueImpl::getAsStr();
  }
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    Instruction *I = dyn_cast<Instruction>(&getAssociatedValue());
    if (auto *SI = dyn_cast_or_null<StoreInst>(I)) {
      if (!isDeadStore(A, *SI))
        return indicatePessimisticFixpoint();
    } else {
      if (!isAssumedSideEffectFree(A, I))
        return indicatePessimisticFixpoint();
      if (!areAllUsesAssumedDead(A, getAssociatedValue()))
        return indicatePessimisticFixpoint();
    }
    return ChangeStatus::UNCHANGED;
  }
 
  bool isRemovableStore() const override {
    return isAssumed(IS_REMOVABLE) && isa<StoreInst>(&getAssociatedValue());
  }
 
  /// See AbstractAttribute::manifest(...).
  ChangeStatus manifest(Attributor &A) override {
    Value &V = getAssociatedValue();
    if (auto *I = dyn_cast<Instruction>(&V)) {
      // If we get here we basically know the users are all dead. We check if
      // isAssumedSideEffectFree returns true here again because it might not be
      // the case and only the users are dead but the instruction (=call) is
      // still needed.
      if (isa<StoreInst>(I) ||
          (isAssumedSideEffectFree(A, I) && !isa<InvokeInst>(I))) {
        A.deleteAfterManifest(*I);
        return ChangeStatus::CHANGED;
      }
    }
    return ChangeStatus::UNCHANGED;
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override {
    STATS_DECLTRACK_FLOATING_ATTR(IsDead)
  }
};
 
struct AAIsDeadArgument : public AAIsDeadFloating {
  AAIsDeadArgument(const IRPosition &IRP, Attributor &A)
      : AAIsDeadFloating(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    AAIsDeadFloating::initialize(A);
    if (!A.isFunctionIPOAmendable(*getAnchorScope()))
      indicatePessimisticFixpoint();
  }
 
  /// See AbstractAttribute::manifest(...).
  ChangeStatus manifest(Attributor &A) override {
    Argument &Arg = *getAssociatedArgument();
    if (A.isValidFunctionSignatureRewrite(Arg, /* ReplacementTypes */ {}))
      if (A.registerFunctionSignatureRewrite(
              Arg, /* ReplacementTypes */ {},
              Attributor::ArgumentReplacementInfo::CalleeRepairCBTy{},
              Attributor::ArgumentReplacementInfo::ACSRepairCBTy{})) {
        return ChangeStatus::CHANGED;
      }
    return ChangeStatus::UNCHANGED;
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(IsDead) }
};
 
struct AAIsDeadCallSiteArgument : public AAIsDeadValueImpl {
  AAIsDeadCallSiteArgument(const IRPosition &IRP, Attributor &A)
      : AAIsDeadValueImpl(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    AAIsDeadValueImpl::initialize(A);
    if (isa<UndefValue>(getAssociatedValue()))
      indicatePessimisticFixpoint();
  }
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    // TODO: Once we have call site specific value information we can provide
    //       call site specific liveness information and then it makes
    //       sense to specialize attributes for call sites arguments instead of
    //       redirecting requests to the callee argument.
    Argument *Arg = getAssociatedArgument();
    if (!Arg)
      return indicatePessimisticFixpoint();
    const IRPosition &ArgPos = IRPosition::argument(*Arg);
    auto &ArgAA = A.getAAFor<AAIsDead>(*this, ArgPos, DepClassTy::REQUIRED);
    return clampStateAndIndicateChange(getState(), ArgAA.getState());
  }
 
  /// See AbstractAttribute::manifest(...).
  ChangeStatus manifest(Attributor &A) override {
    CallBase &CB = cast<CallBase>(getAnchorValue());
    Use &U = CB.getArgOperandUse(getCallSiteArgNo());
    assert(!isa<UndefValue>(U.get()) &&
           "Expected undef values to be filtered out!");
    UndefValue &UV = *UndefValue::get(U->getType());
    if (A.changeUseAfterManifest(U, UV))
      return ChangeStatus::CHANGED;
    return ChangeStatus::UNCHANGED;
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(IsDead) }
};
 
struct AAIsDeadCallSiteReturned : public AAIsDeadFloating {
  AAIsDeadCallSiteReturned(const IRPosition &IRP, Attributor &A)
      : AAIsDeadFloating(IRP, A) {}
 
  /// See AAIsDead::isAssumedDead().
  bool isAssumedDead() const override {
    return AAIsDeadFloating::isAssumedDead() && IsAssumedSideEffectFree;
  }
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    AAIsDeadFloating::initialize(A);
    if (isa<UndefValue>(getAssociatedValue())) {
      indicatePessimisticFixpoint();
      return;
    }
 
    // We track this separately as a secondary state.
    IsAssumedSideEffectFree = isAssumedSideEffectFree(A, getCtxI());
  }
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    ChangeStatus Changed = ChangeStatus::UNCHANGED;
    if (IsAssumedSideEffectFree && !isAssumedSideEffectFree(A, getCtxI())) {
      IsAssumedSideEffectFree = false;
      Changed = ChangeStatus::CHANGED;
    }
    if (!areAllUsesAssumedDead(A, getAssociatedValue()))
      return indicatePessimisticFixpoint();
    return Changed;
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override {
    if (IsAssumedSideEffectFree)
      STATS_DECLTRACK_CSRET_ATTR(IsDead)
    else
      STATS_DECLTRACK_CSRET_ATTR(UnusedResult)
  }
 
  /// See AbstractAttribute::getAsStr().
  const std::string getAsStr() const override {
    return isAssumedDead()
               ? "assumed-dead"
               : (getAssumed() ? "assumed-dead-users" : "assumed-live");
  }
 
private:
  bool IsAssumedSideEffectFree = true;
};
 
struct AAIsDeadReturned : public AAIsDeadValueImpl {
  AAIsDeadReturned(const IRPosition &IRP, Attributor &A)
      : AAIsDeadValueImpl(IRP, A) {}
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
 
    bool UsedAssumedInformation = false;
    A.checkForAllInstructions([](Instruction &) { return true; }, *this,
                              {Instruction::Ret}, UsedAssumedInformation);
 
    auto PredForCallSite = [&](AbstractCallSite ACS) {
      if (ACS.isCallbackCall() || !ACS.getInstruction())
        return false;
      return areAllUsesAssumedDead(A, *ACS.getInstruction());
    };
 
    if (!A.checkForAllCallSites(PredForCallSite, *this, true,
                                UsedAssumedInformation))
      return indicatePessimisticFixpoint();
 
    return ChangeStatus::UNCHANGED;
  }
 
  /// See AbstractAttribute::manifest(...).
  ChangeStatus manifest(Attributor &A) override {
    // TODO: Rewrite the signature to return void?
    bool AnyChange = false;
    UndefValue &UV = *UndefValue::get(getAssociatedFunction()->getReturnType());
    auto RetInstPred = [&](Instruction &I) {
      ReturnInst &RI = cast<ReturnInst>(I);
      if (!isa<UndefValue>(RI.getReturnValue()))
        AnyChange |= A.changeUseAfterManifest(RI.getOperandUse(0), UV);
      return true;
    };
    bool UsedAssumedInformation = false;
    A.checkForAllInstructions(RetInstPred, *this, {Instruction::Ret},
                              UsedAssumedInformation);
    return AnyChange ? ChangeStatus::CHANGED : ChangeStatus::UNCHANGED;
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(IsDead) }
};
 
struct AAIsDeadFunction : public AAIsDead {
  AAIsDeadFunction(const IRPosition &IRP, Attributor &A) : AAIsDead(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    Function *F = getAnchorScope();
    if (!F || F->isDeclaration() || !A.isRunOn(*F)) {
      indicatePessimisticFixpoint();
      return;
    }
    ToBeExploredFrom.insert(&F->getEntryBlock().front());
    assumeLive(A, F->getEntryBlock());
  }
 
  /// See AbstractAttribute::getAsStr().
  const std::string getAsStr() const override {
    return "Live[#BB " + std::to_string(AssumedLiveBlocks.size()) + "/" +
           std::to_string(getAnchorScope()->size()) + "][#TBEP " +
           std::to_string(ToBeExploredFrom.size()) + "][#KDE " +
           std::to_string(KnownDeadEnds.size()) + "]";
  }
 
  /// See AbstractAttribute::manifest(...).
  ChangeStatus manifest(Attributor &A) override {
    assert(getState().isValidState() &&
           "Attempted to manifest an invalid state!");
 
    ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
    Function &F = *getAnchorScope();
 
    if (AssumedLiveBlocks.empty()) {
      A.deleteAfterManifest(F);
      return ChangeStatus::CHANGED;
    }
 
    // Flag to determine if we can change an invoke to a call assuming the
    // callee is nounwind. This is not possible if the personality of the
    // function allows to catch asynchronous exceptions.
    bool Invoke2CallAllowed = !mayCatchAsynchronousExceptions(F);
 
    KnownDeadEnds.set_union(ToBeExploredFrom);
    for (const Instruction *DeadEndI : KnownDeadEnds) {
      auto *CB = dyn_cast<CallBase>(DeadEndI);
      if (!CB)
        continue;
      const auto &NoReturnAA = A.getAndUpdateAAFor<AANoReturn>(
          *this, IRPosition::callsite_function(*CB), DepClassTy::OPTIONAL);
      bool MayReturn = !NoReturnAA.isAssumedNoReturn();
      if (MayReturn && (!Invoke2CallAllowed || !isa<InvokeInst>(CB)))
        continue;
 
      if (auto *II = dyn_cast<InvokeInst>(DeadEndI))
        A.registerInvokeWithDeadSuccessor(const_cast<InvokeInst &>(*II));
      else
        A.changeToUnreachableAfterManifest(
            const_cast<Instruction *>(DeadEndI->getNextNode()));
      HasChanged = ChangeStatus::CHANGED;
    }
 
    STATS_DECL(AAIsDead, BasicBlock, "Number of dead basic blocks deleted.");
    for (BasicBlock &BB : F)
      if (!AssumedLiveBlocks.count(&BB)) {
        A.deleteAfterManifest(BB);
        ++BUILD_STAT_NAME(AAIsDead, BasicBlock);
        HasChanged = ChangeStatus::CHANGED;
      }
 
    return HasChanged;
  }
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override;
 
  bool isEdgeDead(const BasicBlock *From, const BasicBlock *To) const override {
    assert(From->getParent() == getAnchorScope() &&
           To->getParent() == getAnchorScope() &&
           "Used AAIsDead of the wrong function");
    return isValidState() && !AssumedLiveEdges.count(std::make_pair(From, To));
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override {}
 
  /// Returns true if the function is assumed dead.
  bool isAssumedDead() const override { return false; }
 
  /// See AAIsDead::isKnownDead().
  bool isKnownDead() const override { return false; }
 
  /// See AAIsDead::isAssumedDead(BasicBlock *).
  bool isAssumedDead(const BasicBlock *BB) const override {
    assert(BB->getParent() == getAnchorScope() &&
           "BB must be in the same anchor scope function.");
 
    if (!getAssumed())
      return false;
    return !AssumedLiveBlocks.count(BB);
  }
 
  /// See AAIsDead::isKnownDead(BasicBlock *).
  bool isKnownDead(const BasicBlock *BB) const override {
    return getKnown() && isAssumedDead(BB);
  }
 
  /// See AAIsDead::isAssumed(Instruction *I).
  bool isAssumedDead(const Instruction *I) const override {
    assert(I->getParent()->getParent() == getAnchorScope() &&
           "Instruction must be in the same anchor scope function.");
 
    if (!getAssumed())
      return false;
 
    // If it is not in AssumedLiveBlocks then it for sure dead.
    // Otherwise, it can still be after noreturn call in a live block.
    if (!AssumedLiveBlocks.count(I->getParent()))
      return true;
 
    // If it is not after a liveness barrier it is live.
    const Instruction *PrevI = I->getPrevNode();
    while (PrevI) {
      if (KnownDeadEnds.count(PrevI) || ToBeExploredFrom.count(PrevI))
        return true;
      PrevI = PrevI->getPrevNode();
    }
    return false;
  }
 
  /// See AAIsDead::isKnownDead(Instruction *I).
  bool isKnownDead(const Instruction *I) const override {
    return getKnown() && isAssumedDead(I);
  }
 
  /// Assume \p BB is (partially) live now and indicate to the Attributor \p A
  /// that internal function called from \p BB should now be looked at.
  bool assumeLive(Attributor &A, const BasicBlock &BB) {
    if (!AssumedLiveBlocks.insert(&BB).second)
      return false;
 
    // We assume that all of BB is (probably) live now and if there are calls to
    // internal functions we will assume that those are now live as well. This
    // is a performance optimization for blocks with calls to a lot of internal
    // functions. It can however cause dead functions to be treated as live.
    for (const Instruction &I : BB)
      if (const auto *CB = dyn_cast<CallBase>(&I))
        if (const Function *F = CB->getCalledFunction())
          if (F->hasLocalLinkage())
            A.markLiveInternalFunction(*F);
    return true;
  }
 
  /// Collection of instructions that need to be explored again, e.g., we
  /// did assume they do not transfer control to (one of their) successors.
  SmallSetVector<const Instruction *, 8> ToBeExploredFrom;
 
  /// Collection of instructions that are known to not transfer control.
  SmallSetVector<const Instruction *, 8> KnownDeadEnds;
 
  /// Collection of all assumed live edges
  DenseSet<std::pair<const BasicBlock *, const BasicBlock *>> AssumedLiveEdges;
 
  /// Collection of all assumed live BasicBlocks.
  DenseSet<const BasicBlock *> AssumedLiveBlocks;
};
 
static bool
identifyAliveSuccessors(Attributor &A, const CallBase &CB,
                        AbstractAttribute &AA,
                        SmallVectorImpl<const Instruction *> &AliveSuccessors) {
  const IRPosition &IPos = IRPosition::callsite_function(CB);
 
  const auto &NoReturnAA =
      A.getAndUpdateAAFor<AANoReturn>(AA, IPos, DepClassTy::OPTIONAL);
  if (NoReturnAA.isAssumedNoReturn())
    return !NoReturnAA.isKnownNoReturn();
  if (CB.isTerminator())
    AliveSuccessors.push_back(&CB.getSuccessor(0)->front());
  else
    AliveSuccessors.push_back(CB.getNextNode());
  return false;
}
 
static bool
identifyAliveSuccessors(Attributor &A, const InvokeInst &II,
                        AbstractAttribute &AA,
                        SmallVectorImpl<const Instruction *> &AliveSuccessors) {
  bool UsedAssumedInformation =
      identifyAliveSuccessors(A, cast<CallBase>(II), AA, AliveSuccessors);
 
  // First, determine if we can change an invoke to a call assuming the
  // callee is nounwind. This is not possible if the personality of the
  // function allows to catch asynchronous exceptions.
  if (AAIsDeadFunction::mayCatchAsynchronousExceptions(*II.getFunction())) {
    AliveSuccessors.push_back(&II.getUnwindDest()->front());
  } else {
    const IRPosition &IPos = IRPosition::callsite_function(II);
    const auto &AANoUnw =
        A.getAndUpdateAAFor<AANoUnwind>(AA, IPos, DepClassTy::OPTIONAL);
    if (AANoUnw.isAssumedNoUnwind()) {
      UsedAssumedInformation |= !AANoUnw.isKnownNoUnwind();
    } else {
      AliveSuccessors.push_back(&II.getUnwindDest()->front());
    }
  }
  return UsedAssumedInformation;
}
 
static bool
identifyAliveSuccessors(Attributor &A, const BranchInst &BI,
                        AbstractAttribute &AA,
                        SmallVectorImpl<const Instruction *> &AliveSuccessors) {
  bool UsedAssumedInformation = false;
  if (BI.getNumSuccessors() == 1) {
    AliveSuccessors.push_back(&BI.getSuccessor(0)->front());
  } else {
    Optional<Constant *> C =
        A.getAssumedConstant(*BI.getCondition(), AA, UsedAssumedInformation);
    if (!C.hasValue() || isa_and_nonnull<UndefValue>(C.getValue())) {
      // No value yet, assume both edges are dead.
    } else if (isa_and_nonnull<ConstantInt>(*C)) {
      const BasicBlock *SuccBB =
          BI.getSuccessor(1 - cast<ConstantInt>(*C)->getValue().getZExtValue());
      AliveSuccessors.push_back(&SuccBB->front());
    } else {
      AliveSuccessors.push_back(&BI.getSuccessor(0)->front());
      AliveSuccessors.push_back(&BI.getSuccessor(1)->front());
      UsedAssumedInformation = false;
    }
  }
  return UsedAssumedInformation;
}
 
static bool
identifyAliveSuccessors(Attributor &A, const SwitchInst &SI,
                        AbstractAttribute &AA,
                        SmallVectorImpl<const Instruction *> &AliveSuccessors) {
  bool UsedAssumedInformation = false;
  Optional<Constant *> C =
      A.getAssumedConstant(*SI.getCondition(), AA, UsedAssumedInformation);
  if (!C.hasValue() || isa_and_nonnull<UndefValue>(C.getValue())) {
    // No value yet, assume all edges are dead.
  } else if (isa_and_nonnull<ConstantInt>(C.getValue())) {
    for (auto &CaseIt : SI.cases()) {
      if (CaseIt.getCaseValue() == C.getValue()) {
        AliveSuccessors.push_back(&CaseIt.getCaseSuccessor()->front());
        return UsedAssumedInformation;
      }
    }
    AliveSuccessors.push_back(&SI.getDefaultDest()->front());
    return UsedAssumedInformation;
  } else {
    for (const BasicBlock *SuccBB : successors(SI.getParent()))
      AliveSuccessors.push_back(&SuccBB->front());
  }
  return UsedAssumedInformation;
}
 
ChangeStatus AAIsDeadFunction::updateImpl(Attributor &A) {
  ChangeStatus Change = ChangeStatus::UNCHANGED;
 
  LLVM_DEBUG(dbgs() << "[AAIsDead] Live [" << AssumedLiveBlocks.size() << "/"
                    << getAnchorScope()->size() << "] BBs and "
                    << ToBeExploredFrom.size() << " exploration points and "
                    << KnownDeadEnds.size() << " known dead ends\n");
 
  // Copy and clear the list of instructions we need to explore from. It is
  // refilled with instructions the next update has to look at.
  SmallVector<const Instruction *, 8> Worklist(ToBeExploredFrom.begin(),
                                               ToBeExploredFrom.end());
  decltype(ToBeExploredFrom) NewToBeExploredFrom;
 
  SmallVector<const Instruction *, 8> AliveSuccessors;
  while (!Worklist.empty()) {
    const Instruction *I = Worklist.pop_back_val();
    LLVM_DEBUG(dbgs() << "[AAIsDead] Exploration inst: " << *I << "\n");
 
    // Fast forward for uninteresting instructions. We could look for UB here
    // though.
    while (!I->isTerminator() && !isa<CallBase>(I))
      I = I->getNextNode();
 
    AliveSuccessors.clear();
 
    bool UsedAssumedInformation = false;
    switch (I->getOpcode()) {
    // TODO: look for (assumed) UB to backwards propagate "deadness".
    default:
      assert(I->isTerminator() &&
             "Expected non-terminators to be handled already!");
      for (const BasicBlock *SuccBB : successors(I->getParent()))
        AliveSuccessors.push_back(&SuccBB->front());
      break;
    case Instruction::Call:
      UsedAssumedInformation = identifyAliveSuccessors(A, cast<CallInst>(*I),
                                                       *this, AliveSuccessors);
      break;
    case Instruction::Invoke:
      UsedAssumedInformation = identifyAliveSuccessors(A, cast<InvokeInst>(*I),
                                                       *this, AliveSuccessors);
      break;
    case Instruction::Br:
      UsedAssumedInformation = identifyAliveSuccessors(A, cast<BranchInst>(*I),
                                                       *this, AliveSuccessors);
      break;
    case Instruction::Switch:
      UsedAssumedInformation = identifyAliveSuccessors(A, cast<SwitchInst>(*I),
                                                       *this, AliveSuccessors);
      break;
    }
 
    if (UsedAssumedInformation) {
      NewToBeExploredFrom.insert(I);
    } else if (AliveSuccessors.empty() ||
               (I->isTerminator() &&
                AliveSuccessors.size() < I->getNumSuccessors())) {
      if (KnownDeadEnds.insert(I))
        Change = ChangeStatus::CHANGED;
    }
 
    LLVM_DEBUG(dbgs() << "[AAIsDead] #AliveSuccessors: "
                      << AliveSuccessors.size() << " UsedAssumedInformation: "
                      << UsedAssumedInformation << "\n");
 
    for (const Instruction *AliveSuccessor : AliveSuccessors) {
      if (!I->isTerminator()) {
        assert(AliveSuccessors.size() == 1 &&
               "Non-terminator expected to have a single successor!");
        Worklist.push_back(AliveSuccessor);
      } else {
        // record the assumed live edge
        auto Edge = std::make_pair(I->getParent(), AliveSuccessor->getParent());
        if (AssumedLiveEdges.insert(Edge).second)
          Change = ChangeStatus::CHANGED;
        if (assumeLive(A, *AliveSuccessor->getParent()))
          Worklist.push_back(AliveSuccessor);
      }
    }
  }
 
  // Check if the content of ToBeExploredFrom changed, ignore the order.
  if (NewToBeExploredFrom.size() != ToBeExploredFrom.size() ||
      llvm::any_of(NewToBeExploredFrom, [&](const Instruction *I) {
        return !ToBeExploredFrom.count(I);
      })) {
    Change = ChangeStatus::CHANGED;
    ToBeExploredFrom = std::move(NewToBeExploredFrom);
  }
 
  // If we know everything is live there is no need to query for liveness.
  // Instead, indicating a pessimistic fixpoint will cause the state to be
  // "invalid" and all queries to be answered conservatively without lookups.
  // To be in this state we have to (1) finished the exploration and (3) not
  // discovered any non-trivial dead end and (2) not ruled unreachable code
  // dead.
  if (ToBeExploredFrom.empty() &&
      getAnchorScope()->size() == AssumedLiveBlocks.size() &&
      llvm::all_of(KnownDeadEnds, [](const Instruction *DeadEndI) {
        return DeadEndI->isTerminator() && DeadEndI->getNumSuccessors() == 0;
      }))
    return indicatePessimisticFixpoint();
  return Change;
}
 
/// Liveness information for a call sites.
struct AAIsDeadCallSite final : AAIsDeadFunction {
  AAIsDeadCallSite(const IRPosition &IRP, Attributor &A)
      : AAIsDeadFunction(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    // TODO: Once we have call site specific value information we can provide
    //       call site specific liveness information and then it makes
    //       sense to specialize attributes for call sites instead of
    //       redirecting requests to the callee.
    llvm_unreachable("Abstract attributes for liveness are not "
                     "supported for call sites yet!");
  }
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    return indicatePessimisticFixpoint();
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override {}
};
} // namespace
 
/// -------------------- Dereferenceable Argument Attribute --------------------
 
namespace {
struct AADereferenceableImpl : AADereferenceable {
  AADereferenceableImpl(const IRPosition &IRP, Attributor &A)
      : AADereferenceable(IRP, A) {}
  using StateType = DerefState;
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    SmallVector<Attribute, 4> Attrs;
    getAttrs({Attribute::Dereferenceable, Attribute::DereferenceableOrNull},
             Attrs, /* IgnoreSubsumingPositions */ false, &A);
    for (const Attribute &Attr : Attrs)
      takeKnownDerefBytesMaximum(Attr.getValueAsInt());
 
    const IRPosition &IRP = this->getIRPosition();
    NonNullAA = &A.getAAFor<AANonNull>(*this, IRP, DepClassTy::NONE);
 
    bool CanBeNull, CanBeFreed;
    takeKnownDerefBytesMaximum(
        IRP.getAssociatedValue().getPointerDereferenceableBytes(
            A.getDataLayout(), CanBeNull, CanBeFreed));
 
    bool IsFnInterface = IRP.isFnInterfaceKind();
    Function *FnScope = IRP.getAnchorScope();
    if (IsFnInterface && (!FnScope || !A.isFunctionIPOAmendable(*FnScope))) {
      indicatePessimisticFixpoint();
      return;
    }
 
    if (Instruction *CtxI = getCtxI())
      followUsesInMBEC(*this, A, getState(), *CtxI);
  }
 
  /// See AbstractAttribute::getState()
  /// {
  StateType &getState() override { return *this; }
  const StateType &getState() const override { return *this; }
  /// }
 
  /// Helper function for collecting accessed bytes in must-be-executed-context
  void addAccessedBytesForUse(Attributor &A, const Use *U, const Instruction *I,
                              DerefState &State) {
    const Value *UseV = U->get();
    if (!UseV->getType()->isPointerTy())
      return;
 
    Optional<MemoryLocation> Loc = MemoryLocation::getOrNone(I);
    if (!Loc || Loc->Ptr != UseV || !Loc->Size.isPrecise() || I->isVolatile())
      return;
 
    int64_t Offset;
    const Value *Base = GetPointerBaseWithConstantOffset(
        Loc->Ptr, Offset, A.getDataLayout(), /*AllowNonInbounds*/ true);
    if (Base && Base == &getAssociatedValue())
      State.addAccessedBytes(Offset, Loc->Size.getValue());
  }
 
  /// See followUsesInMBEC
  bool followUseInMBEC(Attributor &A, const Use *U, const Instruction *I,
                       AADereferenceable::StateType &State) {
    bool IsNonNull = false;
    bool TrackUse = false;
    int64_t DerefBytes = getKnownNonNullAndDerefBytesForUse(
        A, *this, getAssociatedValue(), U, I, IsNonNull, TrackUse);
    LLVM_DEBUG(dbgs() << "[AADereferenceable] Deref bytes: " << DerefBytes
                      << " for instruction " << *I << "\n");
 
    addAccessedBytesForUse(A, U, I, State);
    State.takeKnownDerefBytesMaximum(DerefBytes);
    return TrackUse;
  }
 
  /// See AbstractAttribute::manifest(...).
  ChangeStatus manifest(Attributor &A) override {
    ChangeStatus Change = AADereferenceable::manifest(A);
    if (isAssumedNonNull() && hasAttr(Attribute::DereferenceableOrNull)) {
      removeAttrs({Attribute::DereferenceableOrNull});
      return ChangeStatus::CHANGED;
    }
    return Change;
  }
 
  void getDeducedAttributes(LLVMContext &Ctx,
                            SmallVectorImpl<Attribute> &Attrs) const override {
    // TODO: Add *_globally support
    if (isAssumedNonNull())
      Attrs.emplace_back(Attribute::getWithDereferenceableBytes(
          Ctx, getAssumedDereferenceableBytes()));
    else
      Attrs.emplace_back(Attribute::getWithDereferenceableOrNullBytes(
          Ctx, getAssumedDereferenceableBytes()));
  }
 
  /// See AbstractAttribute::getAsStr().
  const std::string getAsStr() const override {
    if (!getAssumedDereferenceableBytes())
      return "unknown-dereferenceable";
    return std::string("dereferenceable") +
           (isAssumedNonNull() ? "" : "_or_null") +
           (isAssumedGlobal() ? "_globally" : "") + "<" +
           std::to_string(getKnownDereferenceableBytes()) + "-" +
           std::to_string(getAssumedDereferenceableBytes()) + ">";
  }
};
 
/// Dereferenceable attribute for a floating value.
struct AADereferenceableFloating : AADereferenceableImpl {
  AADereferenceableFloating(const IRPosition &IRP, Attributor &A)
      : AADereferenceableImpl(IRP, A) {}
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    const DataLayout &DL = A.getDataLayout();
 
    auto VisitValueCB = [&](const Value &V, const Instruction *, DerefState &T,
                            bool Stripped) -> bool {
      unsigned IdxWidth =
          DL.getIndexSizeInBits(V.getType()->getPointerAddressSpace());
      APInt Offset(IdxWidth, 0);
      const Value *Base = stripAndAccumulateOffsets(
          A, *this, &V, DL, Offset, /* GetMinOffset */ false,
          /* AllowNonInbounds */ true);
 
      const auto &AA = A.getAAFor<AADereferenceable>(
          *this, IRPosition::value(*Base), DepClassTy::REQUIRED);
      int64_t DerefBytes = 0;
      if (!Stripped && this == &AA) {
        // Use IR information if we did not strip anything.
        // TODO: track globally.
        bool CanBeNull, CanBeFreed;
        DerefBytes =
            Base->getPointerDereferenceableBytes(DL, CanBeNull, CanBeFreed);
        T.GlobalState.indicatePessimisticFixpoint();
      } else {
        const DerefState &DS = AA.getState();
        DerefBytes = DS.DerefBytesState.getAssumed();
        T.GlobalState &= DS.GlobalState;
      }
 
      // For now we do not try to "increase" dereferenceability due to negative
      // indices as we first have to come up with code to deal with loops and
      // for overflows of the dereferenceable bytes.
      int64_t OffsetSExt = Offset.getSExtValue();
      if (OffsetSExt < 0)
        OffsetSExt = 0;
 
      T.takeAssumedDerefBytesMinimum(
          std::max(int64_t(0), DerefBytes - OffsetSExt));
 
      if (this == &AA) {
        if (!Stripped) {
          // If nothing was stripped IR information is all we got.
          T.takeKnownDerefBytesMaximum(
              std::max(int64_t(0), DerefBytes - OffsetSExt));
          T.indicatePessimisticFixpoint();
        } else if (OffsetSExt > 0) {
          // If something was stripped but there is circular reasoning we look
          // for the offset. If it is positive we basically decrease the
          // dereferenceable bytes in a circluar loop now, which will simply
          // drive them down to the known value in a very slow way which we
          // can accelerate.
          T.indicatePessimisticFixpoint();
        }
      }
 
      return T.isValidState();
    };
 
    DerefState T;
    bool UsedAssumedInformation = false;
    if (!genericValueTraversal<DerefState>(A, getIRPosition(), *this, T,
                                           VisitValueCB, getCtxI(),
                                           UsedAssumedInformation))
      return indicatePessimisticFixpoint();
 
    return clampStateAndIndicateChange(getState(), T);
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override {
    STATS_DECLTRACK_FLOATING_ATTR(dereferenceable)
  }
};
 
/// Dereferenceable attribute for a return value.
struct AADereferenceableReturned final
    : AAReturnedFromReturnedValues<AADereferenceable, AADereferenceableImpl> {
  AADereferenceableReturned(const IRPosition &IRP, Attributor &A)
      : AAReturnedFromReturnedValues<AADereferenceable, AADereferenceableImpl>(
            IRP, A) {}
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override {
    STATS_DECLTRACK_FNRET_ATTR(dereferenceable)
  }
};
 
/// Dereferenceable attribute for an argument
struct AADereferenceableArgument final
    : AAArgumentFromCallSiteArguments<AADereferenceable,
                                      AADereferenceableImpl> {
  using Base =
      AAArgumentFromCallSiteArguments<AADereferenceable, AADereferenceableImpl>;
  AADereferenceableArgument(const IRPosition &IRP, Attributor &A)
      : Base(IRP, A) {}
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override {
    STATS_DECLTRACK_ARG_ATTR(dereferenceable)
  }
};
 
/// Dereferenceable attribute for a call site argument.
struct AADereferenceableCallSiteArgument final : AADereferenceableFloating {
  AADereferenceableCallSiteArgument(const IRPosition &IRP, Attributor &A)
      : AADereferenceableFloating(IRP, A) {}
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override {
    STATS_DECLTRACK_CSARG_ATTR(dereferenceable)
  }
};
 
/// Dereferenceable attribute deduction for a call site return value.
struct AADereferenceableCallSiteReturned final
    : AACallSiteReturnedFromReturned<AADereferenceable, AADereferenceableImpl> {
  using Base =
      AACallSiteReturnedFromReturned<AADereferenceable, AADereferenceableImpl>;
  AADereferenceableCallSiteReturned(const IRPosition &IRP, Attributor &A)
      : Base(IRP, A) {}
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override {
    STATS_DECLTRACK_CS_ATTR(dereferenceable);
  }
};
} // namespace
 
// ------------------------ Align Argument Attribute ------------------------
 
namespace {
static unsigned getKnownAlignForUse(Attributor &A, AAAlign &QueryingAA,
                                    Value &AssociatedValue, const Use *U,
                                    const Instruction *I, bool &TrackUse) {
  // We need to follow common pointer manipulation uses to the accesses they
  // feed into.
  if (isa<CastInst>(I)) {
    // Follow all but ptr2int casts.
    TrackUse = !isa<PtrToIntInst>(I);
    return 0;
  }
  if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) {
    if (GEP->hasAllConstantIndices())
      TrackUse = true;
    return 0;
  }
 
  MaybeAlign MA;
  if (const auto *CB = dyn_cast<CallBase>(I)) {
    if (CB->isBundleOperand(U) || CB->isCallee(U))
      return 0;
 
    unsigned ArgNo = CB->getArgOperandNo(U);
    IRPosition IRP = IRPosition::callsite_argument(*CB, ArgNo);
    // As long as we only use known information there is no need to track
    // dependences here.
    auto &AlignAA = A.getAAFor<AAAlign>(QueryingAA, IRP, DepClassTy::NONE);
    MA = MaybeAlign(AlignAA.getKnownAlign());
  }
 
  const DataLayout &DL = A.getDataLayout();
  const Value *UseV = U->get();
  if (auto *SI = dyn_cast<StoreInst>(I)) {
    if (SI->getPointerOperand() == UseV)
      MA = SI->getAlign();
  } else if (auto *LI = dyn_cast<LoadInst>(I)) {
    if (LI->getPointerOperand() == UseV)
      MA = LI->getAlign();
  }
 
  if (!MA || *MA <= QueryingAA.getKnownAlign())
    return 0;
 
  unsigned Alignment = MA->value();
  int64_t Offset;
 
  if (const Value *Base = GetPointerBaseWithConstantOffset(UseV, Offset, DL)) {
    if (Base == &AssociatedValue) {
      // BasePointerAddr + Offset = Alignment * Q for some integer Q.
      // So we can say that the maximum power of two which is a divisor of
      // gcd(Offset, Alignment) is an alignment.
 
      uint32_t gcd =
          greatestCommonDivisor(uint32_t(abs((int32_t)Offset)), Alignment);
      Alignment = llvm::PowerOf2Floor(gcd);
    }
  }
 
  return Alignment;
}
 
struct AAAlignImpl : AAAlign {
  AAAlignImpl(const IRPosition &IRP, Attributor &A) : AAAlign(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    SmallVector<Attribute, 4> Attrs;
    getAttrs({Attribute::Alignment}, Attrs);
    for (const Attribute &Attr : Attrs)
      takeKnownMaximum(Attr.getValueAsInt());
 
    Value &V = getAssociatedValue();
    takeKnownMaximum(V.getPointerAlignment(A.getDataLayout()).value());
 
    if (getIRPosition().isFnInterfaceKind() &&
        (!getAnchorScope() ||
         !A.isFunctionIPOAmendable(*getAssociatedFunction()))) {
      indicatePessimisticFixpoint();
      return;
    }
 
    if (Instruction *CtxI = getCtxI())
      followUsesInMBEC(*this, A, getState(), *CtxI);
  }
 
  /// See AbstractAttribute::manifest(...).
  ChangeStatus manifest(Attributor &A) override {
    ChangeStatus LoadStoreChanged = ChangeStatus::UNCHANGED;
 
    // Check for users that allow alignment annotations.
    Value &AssociatedValue = getAssociatedValue();
    for (const Use &U : AssociatedValue.uses()) {
      if (auto *SI = dyn_cast<StoreInst>(U.getUser())) {
        if (SI->getPointerOperand() == &AssociatedValue)
          if (SI->getAlignment() < getAssumedAlign()) {
            STATS_DECLTRACK(AAAlign, Store,
                            "Number of times alignment added to a store");
            SI->setAlignment(Align(getAssumedAlign()));
            LoadStoreChanged = ChangeStatus::CHANGED;
          }
      } else if (auto *LI = dyn_cast<LoadInst>(U.getUser())) {
        if (LI->getPointerOperand() == &AssociatedValue)
          if (LI->getAlignment() < getAssumedAlign()) {
            LI->setAlignment(Align(getAssumedAlign()));
            STATS_DECLTRACK(AAAlign, Load,
                            "Number of times alignment added to a load");
            LoadStoreChanged = ChangeStatus::CHANGED;
          }
      }
    }
 
    ChangeStatus Changed = AAAlign::manifest(A);
 
    Align InheritAlign =
        getAssociatedValue().getPointerAlignment(A.getDataLayout());
    if (InheritAlign >= getAssumedAlign())
      return LoadStoreChanged;
    return Changed | LoadStoreChanged;
  }
 
  // TODO: Provide a helper to determine the implied ABI alignment and check in
  //       the existing manifest method and a new one for AAAlignImpl that value
  //       to avoid making the alignment explicit if it did not improve.
 
  /// See AbstractAttribute::getDeducedAttributes
  virtual void
  getDeducedAttributes(LLVMContext &Ctx,
                       SmallVectorImpl<Attribute> &Attrs) const override {
    if (getAssumedAlign() > 1)
      Attrs.emplace_back(
          Attribute::getWithAlignment(Ctx, Align(getAssumedAlign())));
  }
 
  /// See followUsesInMBEC
  bool followUseInMBEC(Attributor &A, const Use *U, const Instruction *I,
                       AAAlign::StateType &State) {
    bool TrackUse = false;
 
    unsigned int KnownAlign =
        getKnownAlignForUse(A, *this, getAssociatedValue(), U, I, TrackUse);
    State.takeKnownMaximum(KnownAlign);
 
    return TrackUse;
  }
 
  /// See AbstractAttribute::getAsStr().
  const std::string getAsStr() const override {
    return getAssumedAlign() ? ("align<" + std::to_string(getKnownAlign()) +
                                "-" + std::to_string(getAssumedAlign()) + ">")
                             : "unknown-align";
  }
};
 
/// Align attribute for a floating value.
struct AAAlignFloating : AAAlignImpl {
  AAAlignFloating(const IRPosition &IRP, Attributor &A) : AAAlignImpl(IRP, A) {}
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    const DataLayout &DL = A.getDataLayout();
 
    auto VisitValueCB = [&](Value &V, const Instruction *,
                            AAAlign::StateType &T, bool Stripped) -> bool {
      if (isa<UndefValue>(V) || isa<ConstantPointerNull>(V))
        return true;
      const auto &AA = A.getAAFor<AAAlign>(*this, IRPosition::value(V),
                                           DepClassTy::REQUIRED);
      if (!Stripped && this == &AA) {
        int64_t Offset;
        unsigned Alignment = 1;
        if (const Value *Base =
                GetPointerBaseWithConstantOffset(&V, Offset, DL)) {
          // TODO: Use AAAlign for the base too.
          Align PA = Base->getPointerAlignment(DL);
          // BasePointerAddr + Offset = Alignment * Q for some integer Q.
          // So we can say that the maximum power of two which is a divisor of
          // gcd(Offset, Alignment) is an alignment.
 
          uint32_t gcd = greatestCommonDivisor(uint32_t(abs((int32_t)Offset)),
                                               uint32_t(PA.value()));
          Alignment = llvm::PowerOf2Floor(gcd);
        } else {
          Alignment = V.getPointerAlignment(DL).value();
        }
        // Use only IR information if we did not strip anything.
        T.takeKnownMaximum(Alignment);
        T.indicatePessimisticFixpoint();
      } else {
        // Use abstract attribute information.
        const AAAlign::StateType &DS = AA.getState();
        T ^= DS;
      }
      return T.isValidState();
    };
 
    StateType T;
    bool UsedAssumedInformation = false;
    if (!genericValueTraversal<StateType>(A, getIRPosition(), *this, T,
                                          VisitValueCB, getCtxI(),
                                          UsedAssumedInformation))
      return indicatePessimisticFixpoint();
 
    // TODO: If we know we visited all incoming values, thus no are assumed
    // dead, we can take the known information from the state T.
    return clampStateAndIndicateChange(getState(), T);
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_FLOATING_ATTR(align) }
};
 
/// Align attribute for function return value.
struct AAAlignReturned final
    : AAReturnedFromReturnedValues<AAAlign, AAAlignImpl> {
  using Base = AAReturnedFromReturnedValues<AAAlign, AAAlignImpl>;
  AAAlignReturned(const IRPosition &IRP, Attributor &A) : Base(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    Base::initialize(A);
    Function *F = getAssociatedFunction();
    if (!F || F->isDeclaration())
      indicatePessimisticFixpoint();
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(aligned) }
};
 
/// Align attribute for function argument.
struct AAAlignArgument final
    : AAArgumentFromCallSiteArguments<AAAlign, AAAlignImpl> {
  using Base = AAArgumentFromCallSiteArguments<AAAlign, AAAlignImpl>;
  AAAlignArgument(const IRPosition &IRP, Attributor &A) : Base(IRP, A) {}
 
  /// See AbstractAttribute::manifest(...).
  ChangeStatus manifest(Attributor &A) override {
    // If the associated argument is involved in a must-tail call we give up
    // because we would need to keep the argument alignments of caller and
    // callee in-sync. Just does not seem worth the trouble right now.
    if (A.getInfoCache().isInvolvedInMustTailCall(*getAssociatedArgument()))
      return ChangeStatus::UNCHANGED;
    return Base::manifest(A);
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(aligned) }
};
 
struct AAAlignCallSiteArgument final : AAAlignFloating {
  AAAlignCallSiteArgument(const IRPosition &IRP, Attributor &A)
      : AAAlignFloating(IRP, A) {}
 
  /// See AbstractAttribute::manifest(...).
  ChangeStatus manifest(Attributor &A) override {
    // If the associated argument is involved in a must-tail call we give up
    // because we would need to keep the argument alignments of caller and
    // callee in-sync. Just does not seem worth the trouble right now.
    if (Argument *Arg = getAssociatedArgument())
      if (A.getInfoCache().isInvolvedInMustTailCall(*Arg))
        return ChangeStatus::UNCHANGED;
    ChangeStatus Changed = AAAlignImpl::manifest(A);
    Align InheritAlign =
        getAssociatedValue().getPointerAlignment(A.getDataLayout());
    if (InheritAlign >= getAssumedAlign())
      Changed = ChangeStatus::UNCHANGED;
    return Changed;
  }
 
  /// See AbstractAttribute::updateImpl(Attributor &A).
  ChangeStatus updateImpl(Attributor &A) override {
    ChangeStatus Changed = AAAlignFloating::updateImpl(A);
    if (Argument *Arg = getAssociatedArgument()) {
      // We only take known information from the argument
      // so we do not need to track a dependence.
      const auto &ArgAlignAA = A.getAAFor<AAAlign>(
          *this, IRPosition::argument(*Arg), DepClassTy::NONE);
      takeKnownMaximum(ArgAlignAA.getKnownAlign());
    }
    return Changed;
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(aligned) }
};
 
/// Align attribute deduction for a call site return value.
struct AAAlignCallSiteReturned final
    : AACallSiteReturnedFromReturned<AAAlign, AAAlignImpl> {
  using Base = AACallSiteReturnedFromReturned<AAAlign, AAAlignImpl>;
  AAAlignCallSiteReturned(const IRPosition &IRP, Attributor &A)
      : Base(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    Base::initialize(A);
    Function *F = getAssociatedFunction();
    if (!F || F->isDeclaration())
      indicatePessimisticFixpoint();
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(align); }
};
} // namespace
 
/// ------------------ Function No-Return Attribute ----------------------------
namespace {
struct AANoReturnImpl : public AANoReturn {
  AANoReturnImpl(const IRPosition &IRP, Attributor &A) : AANoReturn(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    AANoReturn::initialize(A);
    Function *F = getAssociatedFunction();
    if (!F || F->isDeclaration())
      indicatePessimisticFixpoint();
  }
 
  /// See AbstractAttribute::getAsStr().
  const std::string getAsStr() const override {
    return getAssumed() ? "noreturn" : "may-return";
  }
 
  /// See AbstractAttribute::updateImpl(Attributor &A).
  virtual ChangeStatus updateImpl(Attributor &A) override {
    auto CheckForNoReturn = [](Instruction &) { return false; };
    bool UsedAssumedInformation = false;
    if (!A.checkForAllInstructions(CheckForNoReturn, *this,
                                   {(unsigned)Instruction::Ret},
                                   UsedAssumedInformation))
      return indicatePessimisticFixpoint();
    return ChangeStatus::UNCHANGED;
  }
};
 
struct AANoReturnFunction final : AANoReturnImpl {
  AANoReturnFunction(const IRPosition &IRP, Attributor &A)
      : AANoReturnImpl(IRP, A) {}
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(noreturn) }
};
 
/// NoReturn attribute deduction for a call sites.
struct AANoReturnCallSite final : AANoReturnImpl {
  AANoReturnCallSite(const IRPosition &IRP, Attributor &A)
      : AANoReturnImpl(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    AANoReturnImpl::initialize(A);
    if (Function *F = getAssociatedFunction()) {
      const IRPosition &FnPos = IRPosition::function(*F);
      auto &FnAA = A.getAAFor<AANoReturn>(*this, FnPos, DepClassTy::REQUIRED);
      if (!FnAA.isAssumedNoReturn())
        indicatePessimisticFixpoint();
    }
  }
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    // TODO: Once we have call site specific value information we can provide
    //       call site specific liveness information and then it makes
    //       sense to specialize attributes for call sites arguments instead of
    //       redirecting requests to the callee argument.
    Function *F = getAssociatedFunction();
    const IRPosition &FnPos = IRPosition::function(*F);
    auto &FnAA = A.getAAFor<AANoReturn>(*this, FnPos, DepClassTy::REQUIRED);
    return clampStateAndIndicateChange(getState(), FnAA.getState());
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(noreturn); }
};
} // namespace
 
/// ----------------------- Instance Info ---------------------------------
 
namespace {
/// A class to hold the state of for no-capture attributes.
struct AAInstanceInfoImpl : public AAInstanceInfo {
  AAInstanceInfoImpl(const IRPosition &IRP, Attributor &A)
      : AAInstanceInfo(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    Value &V = getAssociatedValue();
    if (auto *C = dyn_cast<Constant>(&V)) {
      if (C->isThreadDependent())
        indicatePessimisticFixpoint();
      else
        indicateOptimisticFixpoint();
      return;
    }
    if (auto *CB = dyn_cast<CallBase>(&V))
      if (CB->arg_size() == 0 && !CB->mayHaveSideEffects() &&
          !CB->mayReadFromMemory()) {
        indicateOptimisticFixpoint();
        return;
      }
  }
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    ChangeStatus Changed = ChangeStatus::UNCHANGED;
 
    Value &V = getAssociatedValue();
    const Function *Scope = nullptr;
    if (auto *I = dyn_cast<Instruction>(&V))
      Scope = I->getFunction();
    if (auto *A = dyn_cast<Argument>(&V)) {
      Scope = A->getParent();
      if (!Scope->hasLocalLinkage())
        return Changed;
    }
    if (!Scope)
      return indicateOptimisticFixpoint();
 
    auto &NoRecurseAA = A.getAAFor<AANoRecurse>(
        *this, IRPosition::function(*Scope), DepClassTy::OPTIONAL);
    if (NoRecurseAA.isAssumedNoRecurse())
      return Changed;
 
    auto UsePred = [&](const Use &U, bool &Follow) {
      const Instruction *UserI = dyn_cast<Instruction>(U.getUser());
      if (!UserI || isa<GetElementPtrInst>(UserI) || isa<CastInst>(UserI) ||
          isa<PHINode>(UserI) || isa<SelectInst>(UserI)) {
        Follow = true;
        return true;
      }
      if (isa<LoadInst>(UserI) || isa<CmpInst>(UserI) ||
          (isa<StoreInst>(UserI) &&
           cast<StoreInst>(UserI)->getValueOperand() != U.get()))
        return true;
      if (auto *CB = dyn_cast<CallBase>(UserI)) {
        // This check is not guaranteeing uniqueness but for now that we cannot
        // end up with two versions of \p U thinking it was one.
        if (!CB->getCalledFunction() ||
            !CB->getCalledFunction()->hasLocalLinkage())
          return true;
        if (!CB->isArgOperand(&U))
          return false;
        const auto &ArgInstanceInfoAA = A.getAAFor<AAInstanceInfo>(
            *this, IRPosition::callsite_argument(*CB, CB->getArgOperandNo(&U)),
            DepClassTy::OPTIONAL);
        if (ArgInstanceInfoAA.isAssumedUniqueForAnalysis())
          return true;
      }
      return false;
    };
 
    auto EquivalentUseCB = [&](const Use &OldU, const Use &NewU) {
      if (auto *SI = dyn_cast<StoreInst>(OldU.getUser())) {
        auto *Ptr = SI->getPointerOperand()->stripPointerCasts();
        if (isa<AllocaInst>(Ptr) && AA::isDynamicallyUnique(A, *this, *Ptr))
          return true;
        auto *TLI = A.getInfoCache().getTargetLibraryInfoForFunction(
            *SI->getFunction());
        if (isAllocationFn(Ptr, TLI) && AA::isDynamicallyUnique(A, *this, *Ptr))
          return true;
      }
      return false;
    };
 
    if (!A.checkForAllUses(UsePred, *this, V, /* CheckBBLivenessOnly */ true,
                           DepClassTy::OPTIONAL,
                           /* IgnoreDroppableUses */ true, EquivalentUseCB))
      return indicatePessimisticFixpoint();
 
    return Changed;
  }
 
  /// See AbstractState::getAsStr().
  const std::string getAsStr() const override {
    return isAssumedUniqueForAnalysis() ? "<unique [fAa]>" : "<unknown>";
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override {}
};
 
/// InstanceInfo attribute for floating values.
struct AAInstanceInfoFloating : AAInstanceInfoImpl {
  AAInstanceInfoFloating(const IRPosition &IRP, Attributor &A)
      : AAInstanceInfoImpl(IRP, A) {}
};
 
/// NoCapture attribute for function arguments.
struct AAInstanceInfoArgument final : AAInstanceInfoFloating {
  AAInstanceInfoArgument(const IRPosition &IRP, Attributor &A)
      : AAInstanceInfoFloating(IRP, A) {}
};
 
/// InstanceInfo attribute for call site arguments.
struct AAInstanceInfoCallSiteArgument final : AAInstanceInfoImpl {
  AAInstanceInfoCallSiteArgument(const IRPosition &IRP, Attributor &A)
      : AAInstanceInfoImpl(IRP, A) {}
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    // TODO: Once we have call site specific value information we can provide
    //       call site specific liveness information and then it makes
    //       sense to specialize attributes for call sites arguments instead of
    //       redirecting requests to the callee argument.
    Argument *Arg = getAssociatedArgument();
    if (!Arg)
      return indicatePessimisticFixpoint();
    const IRPosition &ArgPos = IRPosition::argument(*Arg);
    auto &ArgAA =
        A.getAAFor<AAInstanceInfo>(*this, ArgPos, DepClassTy::REQUIRED);
    return clampStateAndIndicateChange(getState(), ArgAA.getState());
  }
};
 
/// InstanceInfo attribute for function return value.
struct AAInstanceInfoReturned final : AAInstanceInfoImpl {
  AAInstanceInfoReturned(const IRPosition &IRP, Attributor &A)
      : AAInstanceInfoImpl(IRP, A) {
    llvm_unreachable("InstanceInfo is not applicable to function returns!");
  }
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    llvm_unreachable("InstanceInfo is not applicable to function returns!");
  }
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    llvm_unreachable("InstanceInfo is not applicable to function returns!");
  }
};
 
/// InstanceInfo attribute deduction for a call site return value.
struct AAInstanceInfoCallSiteReturned final : AAInstanceInfoFloating {
  AAInstanceInfoCallSiteReturned(const IRPosition &IRP, Attributor &A)
      : AAInstanceInfoFloating(IRP, A) {}
};
} // namespace
 
/// ----------------------- Variable Capturing ---------------------------------
 
namespace {
/// A class to hold the state of for no-capture attributes.
struct AANoCaptureImpl : public AANoCapture {
  AANoCaptureImpl(const IRPosition &IRP, Attributor &A) : AANoCapture(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    if (hasAttr(getAttrKind(), /* IgnoreSubsumingPositions */ true)) {
      indicateOptimisticFixpoint();
      return;
    }
    Function *AnchorScope = getAnchorScope();
    if (isFnInterfaceKind() &&
        (!AnchorScope || !A.isFunctionIPOAmendable(*AnchorScope))) {
      indicatePessimisticFixpoint();
      return;
    }
 
    // You cannot "capture" null in the default address space.
    if (isa<ConstantPointerNull>(getAssociatedValue()) &&
        getAssociatedValue().getType()->getPointerAddressSpace() == 0) {
      indicateOptimisticFixpoint();
      return;
    }
 
    const Function *F =
        isArgumentPosition() ? getAssociatedFunction() : AnchorScope;
 
    // Check what state the associated function can actually capture.
    if (F)
      determineFunctionCaptureCapabilities(getIRPosition(), *F, *this);
    else
      indicatePessimisticFixpoint();
  }
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override;
 
  /// see AbstractAttribute::isAssumedNoCaptureMaybeReturned(...).
  virtual void
  getDeducedAttributes(LLVMContext &Ctx,
                       SmallVectorImpl<Attribute> &Attrs) const override {
    if (!isAssumedNoCaptureMaybeReturned())
      return;
 
    if (isArgumentPosition()) {
      if (isAssumedNoCapture())
        Attrs.emplace_back(Attribute::get(Ctx, Attribute::NoCapture));
      else if (ManifestInternal)
        Attrs.emplace_back(Attribute::get(Ctx, "no-capture-maybe-returned"));
    }
  }
 
  /// Set the NOT_CAPTURED_IN_MEM and NOT_CAPTURED_IN_RET bits in \p Known
  /// depending on the ability of the function associated with \p IRP to capture
  /// state in memory and through "returning/throwing", respectively.
  static void determineFunctionCaptureCapabilities(const IRPosition &IRP,
                                                   const Function &F,
                                                   BitIntegerState &State) {
    // TODO: Once we have memory behavior attributes we should use them here.
 
    // If we know we cannot communicate or write to memory, we do not care about
    // ptr2int anymore.
    if (F.onlyReadsMemory() && F.doesNotThrow() &&
        F.getReturnType()->isVoidTy()) {
      State.addKnownBits(NO_CAPTURE);
      return;
    }
 
    // A function cannot capture state in memory if it only reads memory, it can
    // however return/throw state and the state might be influenced by the
    // pointer value, e.g., loading from a returned pointer might reveal a bit.
    if (F.onlyReadsMemory())
      State.addKnownBits(NOT_CAPTURED_IN_MEM);
 
    // A function cannot communicate state back if it does not through
    // exceptions and doesn not return values.
    if (F.doesNotThrow() && F.getReturnType()->isVoidTy())
      State.addKnownBits(NOT_CAPTURED_IN_RET);
 
    // Check existing "returned" attributes.
    int ArgNo = IRP.getCalleeArgNo();
    if (F.doesNotThrow() && ArgNo >= 0) {
      for (unsigned u = 0, e = F.arg_size(); u < e; ++u)
        if (F.hasParamAttribute(u, Attribute::Returned)) {
          if (u == unsigned(ArgNo))
            State.removeAssumedBits(NOT_CAPTURED_IN_RET);
          else if (F.onlyReadsMemory())
            State.addKnownBits(NO_CAPTURE);
          else
            State.addKnownBits(NOT_CAPTURED_IN_RET);
          break;
        }
    }
  }
 
  /// See AbstractState::getAsStr().
  const std::string getAsStr() const override {
    if (isKnownNoCapture())
      return "known not-captured";
    if (isAssumedNoCapture())
      return "assumed not-captured";
    if (isKnownNoCaptureMaybeReturned())
      return "known not-captured-maybe-returned";
    if (isAssumedNoCaptureMaybeReturned())
      return "assumed not-captured-maybe-returned";
    return "assumed-captured";
  }
 
  /// Check the use \p U and update \p State accordingly. Return true if we
  /// should continue to update the state.
  bool checkUse(Attributor &A, AANoCapture::StateType &State, const Use &U,
                bool &Follow) {
    Instruction *UInst = cast<Instruction>(U.getUser());
    LLVM_DEBUG(dbgs() << "[AANoCapture] Check use: " << *U.get() << " in "
                      << *UInst << "\n");
 
    // Deal with ptr2int by following uses.
    if (isa<PtrToIntInst>(UInst)) {
      LLVM_DEBUG(dbgs() << " - ptr2int assume the worst!\n");
      return isCapturedIn(State, /* Memory */ true, /* Integer */ true,
                          /* Return */ true);
    }
 
    // For stores we already checked if we can follow them, if they make it
    // here we give up.
    if (isa<StoreInst>(UInst))
      return isCapturedIn(State, /* Memory */ true, /* Integer */ false,
                          /* Return */ false);
 
    // Explicitly catch return instructions.
    if (isa<ReturnInst>(UInst)) {
      if (UInst->getFunction() == getAnchorScope())
        return isCapturedIn(State, /* Memory */ false, /* Integer */ false,
                            /* Return */ true);
      return isCapturedIn(State, /* Memory */ true, /* Integer */ true,
                          /* Return */ true);
    }
 
    // For now we only use special logic for call sites. However, the tracker
    // itself knows about a lot of other non-capturing cases already.
    auto *CB = dyn_cast<CallBase>(UInst);
    if (!CB || !CB->isArgOperand(&U))
      return isCapturedIn(State, /* Memory */ true, /* Integer */ true,
                          /* Return */ true);
 
    unsigned ArgNo = CB->getArgOperandNo(&U);
    const IRPosition &CSArgPos = IRPosition::callsite_argument(*CB, ArgNo);
    // If we have a abstract no-capture attribute for the argument we can use
    // it to justify a non-capture attribute here. This allows recursion!
    auto &ArgNoCaptureAA =
        A.getAAFor<AANoCapture>(*this, CSArgPos, DepClassTy::REQUIRED);
    if (ArgNoCaptureAA.isAssumedNoCapture())
      return isCapturedIn(State, /* Memory */ false, /* Integer */ false,
                          /* Return */ false);
    if (ArgNoCaptureAA.isAssumedNoCaptureMaybeReturned()) {
      Follow = true;
      return isCapturedIn(State, /* Memory */ false, /* Integer */ false,
                          /* Return */ false);
    }
 
    // Lastly, we could not find a reason no-capture can be assumed so we don't.
    return isCapturedIn(State, /* Memory */ true, /* Integer */ true,
                        /* Return */ true);
  }
 
  /// Update \p State according to \p CapturedInMem, \p CapturedInInt, and
  /// \p CapturedInRet, then return true if we should continue updating the
  /// state.
  static bool isCapturedIn(AANoCapture::StateType &State, bool CapturedInMem,
                           bool CapturedInInt, bool CapturedInRet) {
    LLVM_DEBUG(dbgs() << " - captures [Mem " << CapturedInMem << "|Int "
                      << CapturedInInt << "|Ret " << CapturedInRet << "]\n");
    if (CapturedInMem)
      State.removeAssumedBits(AANoCapture::NOT_CAPTURED_IN_MEM);
    if (CapturedInInt)
      State.removeAssumedBits(AANoCapture::NOT_CAPTURED_IN_INT);
    if (CapturedInRet)
      State.removeAssumedBits(AANoCapture::NOT_CAPTURED_IN_RET);
    return State.isAssumed(AANoCapture::NO_CAPTURE_MAYBE_RETURNED);
  }
};
 
ChangeStatus AANoCaptureImpl::updateImpl(Attributor &A) {
  const IRPosition &IRP = getIRPosition();
  Value *V = isArgumentPosition() ? IRP.getAssociatedArgument()
                                  : &IRP.getAssociatedValue();
  if (!V)
    return indicatePessimisticFixpoint();
 
  const Function *F =
      isArgumentPosition() ? IRP.getAssociatedFunction() : IRP.getAnchorScope();
  assert(F && "Expected a function!");
  const IRPosition &FnPos = IRPosition::function(*F);
 
  AANoCapture::StateType T;
 
  // Readonly means we cannot capture through memory.
  bool IsKnown;
  if (AA::isAssumedReadOnly(A, FnPos, *this, IsKnown)) {
    T.addKnownBits(NOT_CAPTURED_IN_MEM);
    if (IsKnown)
      addKnownBits(NOT_CAPTURED_IN_MEM);
  }
 
  // Make sure all returned values are different than the underlying value.
  // TODO: we could do this in a more sophisticated way inside
  //       AAReturnedValues, e.g., track all values that escape through returns
  //       directly somehow.
  auto CheckReturnedArgs = [&](const AAReturnedValues &RVAA) {
    bool SeenConstant = false;
    for (auto &It : RVAA.returned_values()) {
      if (isa<Constant>(It.first)) {
        if (SeenConstant)
          return false;
        SeenConstant = true;
      } else if (!isa<Argument>(It.first) ||
                 It.first == getAssociatedArgument())
        return false;
    }
    return true;
  };
 
  const auto &NoUnwindAA =
      A.getAAFor<AANoUnwind>(*this, FnPos, DepClassTy::OPTIONAL);
  if (NoUnwindAA.isAssumedNoUnwind()) {
    bool IsVoidTy = F->getReturnType()->isVoidTy();
    const AAReturnedValues *RVAA =
        IsVoidTy ? nullptr
                 : &A.getAAFor<AAReturnedValues>(*this, FnPos,
 
                                                 DepClassTy::OPTIONAL);
    if (IsVoidTy || CheckReturnedArgs(*RVAA)) {
      T.addKnownBits(NOT_CAPTURED_IN_RET);
      if (T.isKnown(NOT_CAPTURED_IN_MEM))
        return ChangeStatus::UNCHANGED;
      if (NoUnwindAA.isKnownNoUnwind() &&
          (IsVoidTy || RVAA->getState().isAtFixpoint())) {
        addKnownBits(NOT_CAPTURED_IN_RET);
        if (isKnown(NOT_CAPTURED_IN_MEM))
          return indicateOptimisticFixpoint();
      }
    }
  }
 
  auto IsDereferenceableOrNull = [&](Value *O, const DataLayout &DL) {
    const auto &DerefAA = A.getAAFor<AADereferenceable>(
        *this, IRPosition::value(*O), DepClassTy::OPTIONAL);
    return DerefAA.getAssumedDereferenceableBytes();
  };
 
  auto UseCheck = [&](const Use &U, bool &Follow) -> bool {
    switch (DetermineUseCaptureKind(U, IsDereferenceableOrNull)) {
    case UseCaptureKind::NO_CAPTURE:
      return true;
    case UseCaptureKind::MAY_CAPTURE:
      return checkUse(