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/ArrayRef.h"
#include "llvm/ADT/DenseMapInfo.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/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AssumeBundleQueries.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/CaptureTracking.h"
#include "llvm/Analysis/CycleAnalysis.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/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/GlobalValue.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InlineAsm.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/IntrinsicsAMDGPU.h"
#include "llvm/IR/IntrinsicsNVPTX.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/MDBuilder.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/TypeSize.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/CallPromotionUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include <cassert>
#include <numeric>
#include <optional>
#include <string>
 
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;
 
template <> unsigned llvm::PotentialLLVMValuesState::MaxPotentialValues = -1;
 
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<int> MaxPotentialValuesIterations(
    "attributor-max-potential-values-iterations", cl::Hidden,
    cl::desc(
        "Maximum number of iterations we keep dismantling potential values."),
    cl::init(64));
 
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(AANonConvergent)
PIPE_OPERATOR(AAWillReturn)
PIPE_OPERATOR(AANoReturn)
PIPE_OPERATOR(AANonNull)
PIPE_OPERATOR(AAMustProgress)
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(AAIntraFnReachability)
PIPE_OPERATOR(AAMemoryBehavior)
PIPE_OPERATOR(AAMemoryLocation)
PIPE_OPERATOR(AAValueConstantRange)
PIPE_OPERATOR(AAPrivatizablePtr)
PIPE_OPERATOR(AAUndefinedBehavior)
PIPE_OPERATOR(AAPotentialConstantValues)
PIPE_OPERATOR(AAPotentialValues)
PIPE_OPERATOR(AANoUndef)
PIPE_OPERATOR(AANoFPClass)
PIPE_OPERATOR(AACallEdges)
PIPE_OPERATOR(AAInterFnReachability)
PIPE_OPERATOR(AAPointerInfo)
PIPE_OPERATOR(AAAssumptionInfo)
PIPE_OPERATOR(AAUnderlyingObjects)
PIPE_OPERATOR(AAAddressSpace)
PIPE_OPERATOR(AAAllocationInfo)
PIPE_OPERATOR(AAIndirectCallInfo)
PIPE_OPERATOR(AAGlobalValueInfo)
PIPE_OPERATOR(AADenormalFPMath)
 
#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
 
static bool mayBeInCycle(const CycleInfo *CI, const Instruction *I,
                         bool HeaderOnly, Cycle **CPtr = nullptr) {
  if (!CI)
    return true;
  auto *BB = I->getParent();
  auto *C = CI->getCycle(BB);
  if (!C)
    return false;
  if (CPtr)
    *CPtr = C;
  return !HeaderOnly || BB == C->getHeader();
}
 
/// Checks if a type could have padding bytes.
static bool isDenselyPacked(Type *Ty, const DataLayout &DL) {
  // There is no size information, so be conservative.
  if (!Ty->isSized())
    return false;
 
  // If the alloc size is not equal to the storage size, then there are padding
  // bytes. For x86_fp80 on x86-64, size: 80 alloc size: 128.
  if (DL.getTypeSizeInBits(Ty) != DL.getTypeAllocSizeInBits(Ty))
    return false;
 
  // FIXME: This isn't the right way to check for padding in vectors with
  // non-byte-size elements.
  if (VectorType *SeqTy = dyn_cast<VectorType>(Ty))
    return isDenselyPacked(SeqTy->getElementType(), DL);
 
  // For array types, check for padding within members.
  if (ArrayType *SeqTy = dyn_cast<ArrayType>(Ty))
    return isDenselyPacked(SeqTy->getElementType(), DL);
 
  if (!isa<StructType>(Ty))
    return true;
 
  // Check for padding within and between elements of a struct.
  StructType *StructTy = cast<StructType>(Ty);
  const StructLayout *Layout = DL.getStructLayout(StructTy);
  uint64_t StartPos = 0;
  for (unsigned I = 0, E = StructTy->getNumElements(); I < E; ++I) {
    Type *ElTy = StructTy->getElementType(I);
    if (!isDenselyPacked(ElTy, DL))
      return false;
    if (StartPos != Layout->getElementOffsetInBits(I))
      return false;
    StartPos += DL.getTypeAllocSizeInBits(ElTy);
  }
 
  return true;
}
 
/// 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.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;
}
 
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);
    if (!ValueConstantRangeAA)
      return false;
    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,
          Attribute::AttrKind IRAttributeKind = AAType::IRAttributeKind,
          bool RecurseForSelectAndPHI = true>
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.
  std::optional<StateType> T;
 
  // Callback for each possibly returned value.
  auto CheckReturnValue = [&](Value &RV) -> bool {
    const IRPosition &RVPos = IRPosition::value(RV, CBContext);
    // If possible, use the hasAssumedIRAttr interface.
    if (Attribute::isEnumAttrKind(IRAttributeKind)) {
      bool IsKnown;
      return AA::hasAssumedIRAttr<IRAttributeKind>(
          A, &QueryingAA, RVPos, DepClassTy::REQUIRED, IsKnown);
    }
 
    const AAType *AA =
        A.getAAFor<AAType>(QueryingAA, RVPos, DepClassTy::REQUIRED);
    if (!AA)
      return false;
    LLVM_DEBUG(dbgs() << "[Attributor] RV: " << RV
                      << " AA: " << AA->getAsStr(&A) << " @ " << RVPos << "\n");
    const StateType &AAS = AA->getState();
    if (!T)
      T = StateType::getBestState(AAS);
    *T &= AAS;
    LLVM_DEBUG(dbgs() << "[Attributor] AA State: " << AAS << " RV State: " << T
                      << "\n");
    return T->isValidState();
  };
 
  if (!A.checkForAllReturnedValues(CheckReturnValue, QueryingAA,
                                   AA::ValueScope::Intraprocedural,
                                   RecurseForSelectAndPHI))
    S.indicatePessimisticFixpoint();
  else if (T)
    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,
          Attribute::AttrKind IRAttributeKind = AAType::IRAttributeKind,
          bool RecurseForSelectAndPHI = true>
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, IRAttributeKind, RecurseForSelectAndPHI>(
        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,
          Attribute::AttrKind IRAttributeKind = AAType::IRAttributeKind>
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.
  std::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;
 
    // If possible, use the hasAssumedIRAttr interface.
    if (Attribute::isEnumAttrKind(IRAttributeKind)) {
      bool IsKnown;
      return AA::hasAssumedIRAttr<IRAttributeKind>(
          A, &QueryingAA, ACSArgPos, DepClassTy::REQUIRED, IsKnown);
    }
 
    const AAType *AA =
        A.getAAFor<AAType>(QueryingAA, ACSArgPos, DepClassTy::REQUIRED);
    if (!AA)
      return false;
    LLVM_DEBUG(dbgs() << "[Attributor] ACS: " << *ACS.getInstruction()
                      << " AA: " << AA->getAsStr(&A) << " @" << ACSArgPos
                      << "\n");
    const StateType &AAS = AA->getState();
    if (!T)
      T = StateType::getBestState(AAS);
    *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)
    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,
          Attribute::AttrKind IRAttributeKind = AAType::IRAttributeKind>
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 IRPosition CBArgPos = IRPosition::callsite_argument(*CBContext, ArgNo);
 
  // If possible, use the hasAssumedIRAttr interface.
  if (Attribute::isEnumAttrKind(IRAttributeKind)) {
    bool IsKnown;
    return AA::hasAssumedIRAttr<IRAttributeKind>(
        A, &QueryingAttribute, CBArgPos, DepClassTy::REQUIRED, IsKnown);
  }
 
  const auto *AA =
      A.getAAFor<AAType>(QueryingAttribute, CBArgPos, DepClassTy::REQUIRED);
  if (!AA)
    return false;
  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,
          Attribute::AttrKind IRAttributeKind = AAType::IRAttributeKind>
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,
                                              IRAttributeKind>(
              A, *this, this->getIRPosition(), S);
      if (Success)
        return clampStateAndIndicateChange<StateType>(this->getState(), S);
    }
    clampCallSiteArgumentStates<AAType, StateType, IRAttributeKind>(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,
          Attribute::AttrKind IRAttributeKind = AAType::IRAttributeKind>
struct AACalleeToCallSite : public BaseType {
  AACalleeToCallSite(const IRPosition &IRP, Attributor &A) : BaseType(IRP, A) {}
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    auto IRPKind = this->getIRPosition().getPositionKind();
    assert((IRPKind == IRPosition::IRP_CALL_SITE_RETURNED ||
            IRPKind == IRPosition::IRP_CALL_SITE) &&
           "Can only wrap function returned positions for call site "
           "returned positions!");
    auto &S = this->getState();
 
    CallBase &CB = cast<CallBase>(this->getAnchorValue());
    if (IntroduceCallBaseContext)
      LLVM_DEBUG(dbgs() << "[Attributor] Introducing call base context:" << CB
                        << "\n");
 
    ChangeStatus Changed = ChangeStatus::UNCHANGED;
    auto CalleePred = [&](ArrayRef<const Function *> Callees) {
      for (const Function *Callee : Callees) {
        IRPosition FnPos =
            IRPKind == llvm::IRPosition::IRP_CALL_SITE_RETURNED
                ? IRPosition::returned(*Callee,
                                       IntroduceCallBaseContext ? &CB : nullptr)
                : IRPosition::function(
                      *Callee, IntroduceCallBaseContext ? &CB : nullptr);
        // If possible, use the hasAssumedIRAttr interface.
        if (Attribute::isEnumAttrKind(IRAttributeKind)) {
          bool IsKnown;
          if (!AA::hasAssumedIRAttr<IRAttributeKind>(
                  A, this, FnPos, DepClassTy::REQUIRED, IsKnown))
            return false;
          continue;
        }
 
        const AAType *AA =
            A.getAAFor<AAType>(*this, FnPos, DepClassTy::REQUIRED);
        if (!AA)
          return false;
        Changed |= clampStateAndIndicateChange(S, AA->getState());
        if (S.isAtFixpoint())
          return S.isValidState();
      }
      return true;
    };
    if (!A.checkForAllCallees(CalleePred, *this, CB))
      return S.indicatePessimisticFixpoint();
    return Changed;
  }
};
 
/// 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) {
  MustBeExecutedContextExplorer *Explorer =
      A.getInfoCache().getMustBeExecutedContextExplorer();
  if (!Explorer)
    return;
 
  // Container for (transitive) uses of the associated value.
  SetVector<const Use *> Uses;
  for (const Use &U : AA.getIRPosition().getAssociatedValue().uses())
    Uses.insert(&U);
 
  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::Access 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 RangeTy as a key in a DenseMap.
template <> struct DenseMapInfo<AA::RangeTy> {
  static inline AA::RangeTy getEmptyKey() {
    auto EmptyKey = DenseMapInfo<int64_t>::getEmptyKey();
    return AA::RangeTy{EmptyKey, EmptyKey};
  }
 
  static inline AA::RangeTy getTombstoneKey() {
    auto TombstoneKey = DenseMapInfo<int64_t>::getTombstoneKey();
    return AA::RangeTy{TombstoneKey, TombstoneKey};
  }
 
  static unsigned getHashValue(const AA::RangeTy &Range) {
    return detail::combineHashValue(
        DenseMapInfo<int64_t>::getHashValue(Range.Offset),
        DenseMapInfo<int64_t>::getHashValue(Range.Size));
  }
 
  static bool isEqual(const AA::RangeTy &A, const AA::RangeTy B) {
    return A == B;
  }
};
 
/// Helper for AA::PointerInfo::Access 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 {
  /// 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) = default;
 
  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;
    AccessList = R.AccessList;
    OffsetBins = R.OffsetBins;
    RemoteIMap = R.RemoteIMap;
    return *this;
  }
 
  State &operator=(State &&R) {
    if (this == &R)
      return *this;
    std::swap(BS, R.BS);
    std::swap(AccessList, R.AccessList);
    std::swap(OffsetBins, R.OffsetBins);
    std::swap(RemoteIMap, R.RemoteIMap);
    return *this;
  }
 
  /// 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. If an Access already exists for the same \p I and same
  /// \p RemoteI, the two are combined, potentially losing information about
  /// offset and size. The resulting access must now be moved from its original
  /// OffsetBin to the bin for its new offset.
  ///
  /// \Returns CHANGED, if the state changed, UNCHANGED otherwise.
  ChangeStatus addAccess(Attributor &A, const AAPointerInfo::RangeList &Ranges,
                         Instruction &I, std::optional<Value *> Content,
                         AAPointerInfo::AccessKind Kind, Type *Ty,
                         Instruction *RemoteI = nullptr);
 
  AAPointerInfo::const_bin_iterator begin() const { return OffsetBins.begin(); }
  AAPointerInfo::const_bin_iterator end() const { return OffsetBins.end(); }
  int64_t numOffsetBins() const { return OffsetBins.size(); }
 
  const AAPointerInfo::Access &getAccess(unsigned Index) const {
    return AccessList[Index];
  }
 
protected:
  // Every memory instruction results in an Access object. We maintain a list of
  // all Access objects that we own, along with the following maps:
  //
  // - OffsetBins: RangeTy -> { Access }
  // - RemoteIMap: RemoteI x LocalI -> Access
  //
  // A RemoteI is any instruction that accesses memory. RemoteI is different
  // from LocalI if and only if LocalI is a call; then RemoteI is some
  // instruction in the callgraph starting from LocalI. Multiple paths in the
  // callgraph from LocalI to RemoteI may produce multiple accesses, but these
  // are all combined into a single Access object. This may result in loss of
  // information in RangeTy in the Access object.
  SmallVector<AAPointerInfo::Access> AccessList;
  AAPointerInfo::OffsetBinsTy OffsetBins;
  DenseMap<const Instruction *, SmallVector<unsigned>> RemoteIMap;
 
  /// See AAPointerInfo::forallInterferingAccesses.
  bool forallInterferingAccesses(
      AA::RangeTy Range,
      function_ref<bool(const AAPointerInfo::Access &, bool)> CB) const {
    if (!isValidState())
      return false;
 
    for (const auto &It : OffsetBins) {
      AA::RangeTy ItRange = It.getFirst();
      if (!Range.mayOverlap(ItRange))
        continue;
      bool IsExact = Range == ItRange && !Range.offsetOrSizeAreUnknown();
      for (auto Index : It.getSecond()) {
        auto &Access = AccessList[Index];
        if (!CB(Access, IsExact))
          return false;
      }
    }
    return true;
  }
 
  /// See AAPointerInfo::forallInterferingAccesses.
  bool forallInterferingAccesses(
      Instruction &I,
      function_ref<bool(const AAPointerInfo::Access &, bool)> CB,
      AA::RangeTy &Range) const {
    if (!isValidState())
      return false;
 
    auto LocalList = RemoteIMap.find(&I);
    if (LocalList == RemoteIMap.end()) {
      return true;
    }
 
    for (unsigned Index : LocalList->getSecond()) {
      for (auto &R : AccessList[Index]) {
        Range &= R;
        if (Range.offsetAndSizeAreUnknown())
          break;
      }
    }
    return forallInterferingAccesses(Range, CB);
  }
 
private:
  /// State to track fixpoint and validity.
  BooleanState BS;
};
 
ChangeStatus AA::PointerInfo::State::addAccess(
    Attributor &A, const AAPointerInfo::RangeList &Ranges, Instruction &I,
    std::optional<Value *> Content, AAPointerInfo::AccessKind Kind, Type *Ty,
    Instruction *RemoteI) {
  RemoteI = RemoteI ? RemoteI : &I;
 
  // Check if we have an access for this instruction, if not, simply add it.
  auto &LocalList = RemoteIMap[RemoteI];
  bool AccExists = false;
  unsigned AccIndex = AccessList.size();
  for (auto Index : LocalList) {
    auto &A = AccessList[Index];
    if (A.getLocalInst() == &I) {
      AccExists = true;
      AccIndex = Index;
      break;
    }
  }
 
  auto AddToBins = [&](const AAPointerInfo::RangeList &ToAdd) {
    LLVM_DEBUG(if (ToAdd.size()) dbgs()
                   << "[AAPointerInfo] Inserting access in new offset bins\n";);
 
    for (auto Key : ToAdd) {
      LLVM_DEBUG(dbgs() << "    key " << Key << "\n");
      OffsetBins[Key].insert(AccIndex);
    }
  };
 
  if (!AccExists) {
    AccessList.emplace_back(&I, RemoteI, Ranges, Content, Kind, Ty);
    assert((AccessList.size() == AccIndex + 1) &&
           "New Access should have been at AccIndex");
    LocalList.push_back(AccIndex);
    AddToBins(AccessList[AccIndex].getRanges());
    return ChangeStatus::CHANGED;
  }
 
  // Combine the new Access with the existing Access, and then update the
  // mapping in the offset bins.
  AAPointerInfo::Access Acc(&I, RemoteI, Ranges, Content, Kind, Ty);
  auto &Current = AccessList[AccIndex];
  auto Before = Current;
  Current &= Acc;
  if (Current == Before)
    return ChangeStatus::UNCHANGED;
 
  auto &ExistingRanges = Before.getRanges();
  auto &NewRanges = Current.getRanges();
 
  // Ranges that are in the old access but not the new access need to be removed
  // from the offset bins.
  AAPointerInfo::RangeList ToRemove;
  AAPointerInfo::RangeList::set_difference(ExistingRanges, NewRanges, ToRemove);
  LLVM_DEBUG(if (ToRemove.size()) dbgs()
                 << "[AAPointerInfo] Removing access from old offset bins\n";);
 
  for (auto Key : ToRemove) {
    LLVM_DEBUG(dbgs() << "    key " << Key << "\n");
    assert(OffsetBins.count(Key) && "Existing Access must be in some bin.");
    auto &Bin = OffsetBins[Key];
    assert(Bin.count(AccIndex) &&
           "Expected bin to actually contain the Access.");
    Bin.erase(AccIndex);
  }
 
  // Ranges that are in the new access but not the old access need to be added
  // to the offset bins.
  AAPointerInfo::RangeList ToAdd;
  AAPointerInfo::RangeList::set_difference(NewRanges, ExistingRanges, ToAdd);
  AddToBins(ToAdd);
  return ChangeStatus::CHANGED;
}
 
namespace {
 
/// A helper containing a list of offsets computed for a Use. Ideally this
/// list should be strictly ascending, but we ensure that only when we
/// actually translate the list of offsets to a RangeList.
struct OffsetInfo {
  using VecTy = SmallVector<int64_t>;
  using const_iterator = VecTy::const_iterator;
  VecTy Offsets;
 
  const_iterator begin() const { return Offsets.begin(); }
  const_iterator end() const { return Offsets.end(); }
 
  bool operator==(const OffsetInfo &RHS) const {
    return Offsets == RHS.Offsets;
  }
 
  bool operator!=(const OffsetInfo &RHS) const { return !(*this == RHS); }
 
  void insert(int64_t Offset) { Offsets.push_back(Offset); }
  bool isUnassigned() const { return Offsets.size() == 0; }
 
  bool isUnknown() const {
    if (isUnassigned())
      return false;
    if (Offsets.size() == 1)
      return Offsets.front() == AA::RangeTy::Unknown;
    return false;
  }
 
  void setUnknown() {
    Offsets.clear();
    Offsets.push_back(AA::RangeTy::Unknown);
  }
 
  void addToAll(int64_t Inc) {
    for (auto &Offset : Offsets) {
      Offset += Inc;
    }
  }
 
  /// Copy offsets from \p R into the current list.
  ///
  /// Ideally all lists should be strictly ascending, but we defer that to the
  /// actual use of the list. So we just blindly append here.
  void merge(const OffsetInfo &R) { Offsets.append(R.Offsets); }
};
 
#ifndef NDEBUG
static raw_ostream &operator<<(raw_ostream &OS, const OffsetInfo &OI) {
  ListSeparator LS;
  OS << "[";
  for (auto Offset : OI) {
    OS << LS << Offset;
  }
  OS << "]";
  return OS;
}
#endif // NDEBUG
 
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::getAsStr().
  const std::string getAsStr(Attributor *A) const override {
    return std::string("PointerInfo ") +
           (isValidState() ? (std::string("#") +
                              std::to_string(OffsetBins.size()) + " bins")
                           : "<invalid>");
  }
 
  /// See AbstractAttribute::manifest(...).
  ChangeStatus manifest(Attributor &A) override {
    return AAPointerInfo::manifest(A);
  }
 
  virtual const_bin_iterator begin() const override { return State::begin(); }
  virtual const_bin_iterator end() const override { return State::end(); }
  virtual int64_t numOffsetBins() const override {
    return State::numOffsetBins();
  }
 
  bool forallInterferingAccesses(
      AA::RangeTy Range,
      function_ref<bool(const AAPointerInfo::Access &, bool)> CB)
      const override {
    return State::forallInterferingAccesses(Range, CB);
  }
 
  bool forallInterferingAccesses(
      Attributor &A, const AbstractAttribute &QueryingAA, Instruction &I,
      bool FindInterferingWrites, bool FindInterferingReads,
      function_ref<bool(const Access &, bool)> UserCB, bool &HasBeenWrittenTo,
      AA::RangeTy &Range,
      function_ref<bool(const Access &)> SkipCB) const override {
    HasBeenWrittenTo = false;
 
    SmallPtrSet<const Access *, 8> DominatingWrites;
    SmallVector<std::pair<const Access *, bool>, 8> InterferingAccesses;
 
    Function &Scope = *I.getFunction();
    bool IsKnownNoSync;
    bool IsAssumedNoSync = AA::hasAssumedIRAttr<Attribute::NoSync>(
        A, &QueryingAA, IRPosition::function(Scope), DepClassTy::OPTIONAL,
        IsKnownNoSync);
    const auto *ExecDomainAA = A.lookupAAFor<AAExecutionDomain>(
        IRPosition::function(Scope), &QueryingAA, DepClassTy::NONE);
    bool AllInSameNoSyncFn = IsAssumedNoSync;
    bool InstIsExecutedByInitialThreadOnly =
        ExecDomainAA && ExecDomainAA->isExecutedByInitialThreadOnly(I);
 
    // If the function is not ending in aligned barriers, we need the stores to
    // be in aligned barriers. The load being in one is not sufficient since the
    // store might be executed by a thread that disappears after, causing the
    // aligned barrier guarding the load to unblock and the load to read a value
    // that has no CFG path to the load.
    bool InstIsExecutedInAlignedRegion =
        FindInterferingReads && ExecDomainAA &&
        ExecDomainAA->isExecutedInAlignedRegion(A, I);
 
    if (InstIsExecutedInAlignedRegion || InstIsExecutedByInitialThreadOnly)
      A.recordDependence(*ExecDomainAA, QueryingAA, DepClassTy::OPTIONAL);
 
    InformationCache &InfoCache = A.getInfoCache();
    bool IsThreadLocalObj =
        AA::isAssumedThreadLocalObject(A, getAssociatedValue(), *this);
 
    // 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. Also, thread-local objects do not require threading reasoning.
    // Finally, we can ignore threading if either access is executed in an
    // aligned region.
    auto CanIgnoreThreadingForInst = [&](const Instruction &I) -> bool {
      if (IsThreadLocalObj || AllInSameNoSyncFn)
        return true;
      const auto *FnExecDomainAA =
          I.getFunction() == &Scope
              ? ExecDomainAA
              : A.lookupAAFor<AAExecutionDomain>(
                    IRPosition::function(*I.getFunction()), &QueryingAA,
                    DepClassTy::NONE);
      if (!FnExecDomainAA)
        return false;
      if (InstIsExecutedInAlignedRegion ||
          (FindInterferingWrites &&
           FnExecDomainAA->isExecutedInAlignedRegion(A, I))) {
        A.recordDependence(*FnExecDomainAA, QueryingAA, DepClassTy::OPTIONAL);
        return true;
      }
      if (InstIsExecutedByInitialThreadOnly &&
          FnExecDomainAA->isExecutedByInitialThreadOnly(I)) {
        A.recordDependence(*FnExecDomainAA, QueryingAA, DepClassTy::OPTIONAL);
        return true;
      }
      return false;
    };
 
    // Helper to determine if the access is executed by the same thread as the
    // given instruction, for now it is sufficient to avoid any potential
    // threading effects as we cannot deal with them anyway.
    auto CanIgnoreThreading = [&](const Access &Acc) -> bool {
      return CanIgnoreThreadingForInst(*Acc.getRemoteInst()) ||
             (Acc.getRemoteInst() != Acc.getLocalInst() &&
              CanIgnoreThreadingForInst(*Acc.getLocalInst()));
    };
 
    // TODO: Use inter-procedural reachability and dominance.
    bool IsKnownNoRecurse;
    AA::hasAssumedIRAttr<Attribute::NoRecurse>(
        A, this, IRPosition::function(Scope), DepClassTy::OPTIONAL,
        IsKnownNoRecurse);
 
    // TODO: Use reaching kernels from AAKernelInfo (or move it to
    // AAExecutionDomain) such that we allow scopes other than kernels as long
    // as the reaching kernels are disjoint.
    bool InstInKernel = Scope.hasFnAttribute("kernel");
    bool ObjHasKernelLifetime = false;
    const bool UseDominanceReasoning =
        FindInterferingWrites && IsKnownNoRecurse;
    const DominatorTree *DT =
        InfoCache.getAnalysisResultForFunction<DominatorTreeAnalysis>(Scope);
 
    // 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) {
      if (!AA::isGPU(M))
        return false;
      switch (AA::GPUAddressSpace(V->getType()->getPointerAddressSpace())) {
      case AA::GPUAddressSpace::Shared:
      case AA::GPUAddressSpace::Constant:
      case AA::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();
      ObjHasKernelLifetime = AIFn->hasFnAttribute("kernel");
      bool IsKnownNoRecurse;
      if (AA::hasAssumedIRAttr<Attribute::NoRecurse>(
              A, this, IRPosition::function(*AIFn), DepClassTy::OPTIONAL,
              IsKnownNoRecurse)) {
        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.
      ObjHasKernelLifetime = HasKernelLifetime(GV, *GV->getParent());
      if (ObjHasKernelLifetime)
        IsLiveInCalleeCB = [](const Function &Fn) {
          return !Fn.hasFnAttribute("kernel");
        };
    }
 
    // Set of accesses/instructions that will overwrite the result and are
    // therefore blockers in the reachability traversal.
    AA::InstExclusionSetTy ExclusionSet;
 
    auto AccessCB = [&](const Access &Acc, bool Exact) {
      Function *AccScope = Acc.getRemoteInst()->getFunction();
      bool AccInSameScope = AccScope == &Scope;
 
      // If the object has kernel lifetime we can ignore accesses only reachable
      // by other kernels. For now we only skip accesses *in* other kernels.
      if (InstInKernel && ObjHasKernelLifetime && !AccInSameScope &&
          AccScope->hasFnAttribute("kernel"))
        return true;
 
      if (Exact && Acc.isMustAccess() && Acc.getRemoteInst() != &I) {
        if (Acc.isWrite() || (isa<LoadInst>(I) && Acc.isWriteOrAssumption()))
          ExclusionSet.insert(Acc.getRemoteInst());
      }
 
      if ((!FindInterferingWrites || !Acc.isWriteOrAssumption()) &&
          (!FindInterferingReads || !Acc.isRead()))
        return true;
 
      bool Dominates = FindInterferingWrites && DT && Exact &&
                       Acc.isMustAccess() && AccInSameScope &&
                       DT->dominates(Acc.getRemoteInst(), &I);
      if (Dominates)
        DominatingWrites.insert(&Acc);
 
      // Track if all interesting accesses are in the same `nosync` function as
      // the given instruction.
      AllInSameNoSyncFn &= Acc.getRemoteInst()->getFunction() == &Scope;
 
      InterferingAccesses.push_back({&Acc, Exact});
      return true;
    };
    if (!State::forallInterferingAccesses(I, AccessCB, Range))
      return false;
 
    HasBeenWrittenTo = !DominatingWrites.empty();
 
    // Dominating writes form a chain, find the least/lowest member.
    Instruction *LeastDominatingWriteInst = nullptr;
    for (const Access *Acc : DominatingWrites) {
      if (!LeastDominatingWriteInst) {
        LeastDominatingWriteInst = Acc->getRemoteInst();
      } else if (DT->dominates(LeastDominatingWriteInst,
                               Acc->getRemoteInst())) {
        LeastDominatingWriteInst = Acc->getRemoteInst();
      }
    }
 
    // Helper to determine if we can skip a specific write access.
    auto CanSkipAccess = [&](const Access &Acc, bool Exact) {
      if (SkipCB && SkipCB(Acc))
        return true;
      if (!CanIgnoreThreading(Acc))
        return false;
 
      // Check read (RAW) dependences and write (WAR) dependences as necessary.
      // If we successfully excluded all effects we are interested in, the
      // access can be skipped.
      bool ReadChecked = !FindInterferingReads;
      bool WriteChecked = !FindInterferingWrites;
 
      // If the instruction cannot reach the access, the former does not
      // interfere with what the access reads.
      if (!ReadChecked) {
        if (!AA::isPotentiallyReachable(A, I, *Acc.getRemoteInst(), QueryingAA,
                                        &ExclusionSet, IsLiveInCalleeCB))
          ReadChecked = true;
      }
      // If the instruction cannot be reach from the access, the latter does not
      // interfere with what the instruction reads.
      if (!WriteChecked) {
        if (!AA::isPotentiallyReachable(A, *Acc.getRemoteInst(), I, QueryingAA,
                                        &ExclusionSet, IsLiveInCalleeCB))
          WriteChecked = true;
      }
 
      // If we still might be affected by the write of the access but there are
      // dominating writes in the function of the instruction
      // (HasBeenWrittenTo), we can try to reason that the access is overwritten
      // by them. This would have happend above if they are all in the same
      // function, so we only check the inter-procedural case. Effectively, we
      // want to show that there is no call after the dominting write that might
      // reach the access, and when it returns reach the instruction with the
      // updated value. To this end, we iterate all call sites, check if they
      // might reach the instruction without going through another access
      // (ExclusionSet) and at the same time might reach the access. However,
      // that is all part of AAInterFnReachability.
      if (!WriteChecked && HasBeenWrittenTo &&
          Acc.getRemoteInst()->getFunction() != &Scope) {
 
        const auto *FnReachabilityAA = A.getAAFor<AAInterFnReachability>(
            QueryingAA, IRPosition::function(Scope), DepClassTy::OPTIONAL);
 
        // Without going backwards in the call tree, can we reach the access
        // from the least dominating write. Do not allow to pass the instruction
        // itself either.
        bool Inserted = ExclusionSet.insert(&I).second;
 
        if (!FnReachabilityAA ||
            !FnReachabilityAA->instructionCanReach(
                A, *LeastDominatingWriteInst,
                *Acc.getRemoteInst()->getFunction(), &ExclusionSet))
          WriteChecked = true;
 
        if (Inserted)
          ExclusionSet.erase(&I);
      }
 
      if (ReadChecked && WriteChecked)
        return true;
 
      if (!DT || !UseDominanceReasoning)
        return false;
      if (!DominatingWrites.count(&Acc))
        return false;
      return LeastDominatingWriteInst != Acc.getRemoteInst();
    };
 
    // Run the user callback on all accesses we cannot skip and return if
    // that succeeded for all or not.
    for (auto &It : InterferingAccesses) {
      if ((!AllInSameNoSyncFn && !IsThreadLocalObj && !ExecDomainAA) ||
          !CanSkipAccess(*It.first, It.second)) {
        if (!UserCB(*It.first, It.second))
          return false;
      }
    }
    return true;
  }
 
  ChangeStatus translateAndAddStateFromCallee(Attributor &A,
                                              const AAPointerInfo &OtherAA,
                                              CallBase &CB) {
    using namespace AA::PointerInfo;
    if (!OtherAA.getState().isValidState() || !isValidState())
      return indicatePessimisticFixpoint();
 
    const auto &OtherAAImpl = static_cast<const AAPointerInfoImpl &>(OtherAA);
    bool IsByval = OtherAAImpl.getAssociatedArgument()->hasByValAttr();
 
    // Combine the accesses bin by bin.
    ChangeStatus Changed = ChangeStatus::UNCHANGED;
    const auto &State = OtherAAImpl.getState();
    for (const auto &It : State) {
      for (auto Index : It.getSecond()) {
        const auto &RAcc = State.getAccess(Index);
        if (IsByval && !RAcc.isRead())
          continue;
        bool UsedAssumedInformation = false;
        AccessKind AK = RAcc.getKind();
        auto Content = A.translateArgumentToCallSiteContent(
            RAcc.getContent(), CB, *this, UsedAssumedInformation);
        AK = AccessKind(AK & (IsByval ? AccessKind::AK_R : AccessKind::AK_RW));
        AK = AccessKind(AK | (RAcc.isMayAccess() ? AK_MAY : AK_MUST));
 
        Changed |= addAccess(A, RAcc.getRanges(), CB, Content, AK,
                             RAcc.getType(), RAcc.getRemoteInst());
      }
    }
    return Changed;
  }
 
  ChangeStatus translateAndAddState(Attributor &A, const AAPointerInfo &OtherAA,
                                    const OffsetInfo &Offsets, CallBase &CB) {
    using namespace AA::PointerInfo;
    if (!OtherAA.getState().isValidState() || !isValidState())
      return indicatePessimisticFixpoint();
 
    const auto &OtherAAImpl = static_cast<const AAPointerInfoImpl &>(OtherAA);
 
    // Combine the accesses bin by bin.
    ChangeStatus Changed = ChangeStatus::UNCHANGED;
    const auto &State = OtherAAImpl.getState();
    for (const auto &It : State) {
      for (auto Index : It.getSecond()) {
        const auto &RAcc = State.getAccess(Index);
        for (auto Offset : Offsets) {
          auto NewRanges = Offset == AA::RangeTy::Unknown
                               ? AA::RangeTy::getUnknown()
                               : RAcc.getRanges();
          if (!NewRanges.isUnknown()) {
            NewRanges.addToAllOffsets(Offset);
          }
          Changed |=
              addAccess(A, NewRanges, CB, RAcc.getContent(), RAcc.getKind(),
                        RAcc.getType(), RAcc.getRemoteInst());
        }
      }
    }
    return Changed;
  }
 
  /// Statistic tracking for all AAPointerInfo implementations.
  /// See AbstractAttribute::trackStatistics().
  void trackPointerInfoStatistics(const IRPosition &IRP) const {}
 
  /// Dump the state into \p O.
  void dumpState(raw_ostream &O) {
    for (auto &It : OffsetBins) {
      O << "[" << It.first.Offset << "-" << It.first.Offset + It.first.Size
        << "] : " << It.getSecond().size() << "\n";
      for (auto AccIndex : It.getSecond()) {
        auto &Acc = AccessList[AccIndex];
        O << "     - " << Acc.getKind() << " - " << *Acc.getLocalInst() << "\n";
        if (Acc.getLocalInst() != Acc.getRemoteInst())
          O << "     -->                         " << *Acc.getRemoteInst()
            << "\n";
        if (!Acc.isWrittenValueYetUndetermined()) {
          if (isa_and_nonnull<Function>(Acc.getWrittenValue()))
            O << "       - c: func " << Acc.getWrittenValue()->getName()
              << "\n";
          else if (Acc.getWrittenValue())
            O << "       - c: " << *Acc.getWrittenValue() << "\n";
          else
            O << "       - c: <unknown>\n";
        }
      }
    }
  }
};
 
struct AAPointerInfoFloating : public AAPointerInfoImpl {
  using AccessKind = AAPointerInfo::AccessKind;
  AAPointerInfoFloating(const IRPosition &IRP, Attributor &A)
      : AAPointerInfoImpl(IRP, A) {}
 
  /// Deal with an access and signal if it was handled successfully.
  bool handleAccess(Attributor &A, Instruction &I,
                    std::optional<Value *> Content, AccessKind Kind,
                    SmallVectorImpl<int64_t> &Offsets, ChangeStatus &Changed,
                    Type &Ty) {
    using namespace AA::PointerInfo;
    auto Size = AA::RangeTy::Unknown;
    const DataLayout &DL = A.getDataLayout();
    TypeSize AccessSize = DL.getTypeStoreSize(&Ty);
    if (!AccessSize.isScalable())
      Size = AccessSize.getFixedValue();
 
    // Make a strictly ascending list of offsets as required by addAccess()
    llvm::sort(Offsets);
    auto *Last = std::unique(Offsets.begin(), Offsets.end());
    Offsets.erase(Last, Offsets.end());
 
    VectorType *VT = dyn_cast<VectorType>(&Ty);
    if (!VT || VT->getElementCount().isScalable() ||
        !Content.value_or(nullptr) || !isa<Constant>(*Content) ||
        (*Content)->getType() != VT ||
        DL.getTypeStoreSize(VT->getElementType()).isScalable()) {
      Changed = Changed | addAccess(A, {Offsets, Size}, I, Content, Kind, &Ty);
    } else {
      // Handle vector stores with constant content element-wise.
      // TODO: We could look for the elements or create instructions
      //       representing them.
      // TODO: We need to push the Content into the range abstraction
      //       (AA::RangeTy) to allow different content values for different
      //       ranges. ranges. Hence, support vectors storing different values.
      Type *ElementType = VT->getElementType();
      int64_t ElementSize = DL.getTypeStoreSize(ElementType).getFixedValue();
      auto *ConstContent = cast<Constant>(*Content);
      Type *Int32Ty = Type::getInt32Ty(ElementType->getContext());
      SmallVector<int64_t> ElementOffsets(Offsets.begin(), Offsets.end());
 
      for (int i = 0, e = VT->getElementCount().getFixedValue(); i != e; ++i) {
        Value *ElementContent = ConstantExpr::getExtractElement(
            ConstContent, ConstantInt::get(Int32Ty, i));
 
        // Add the element access.
        Changed = Changed | addAccess(A, {ElementOffsets, ElementSize}, I,
                                      ElementContent, Kind, ElementType);
 
        // Advance the offsets for the next element.
        for (auto &ElementOffset : ElementOffsets)
          ElementOffset += ElementSize;
      }
    }
    return true;
  };
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override;
 
  /// If the indices to \p GEP can be traced to constants, incorporate all
  /// of these into \p UsrOI.
  ///
  /// \return true iff \p UsrOI is updated.
  bool collectConstantsForGEP(Attributor &A, const DataLayout &DL,
                              OffsetInfo &UsrOI, const OffsetInfo &PtrOI,
                              const GEPOperator *GEP);
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override {
    AAPointerInfoImpl::trackPointerInfoStatistics(getIRPosition());
  }
};
 
bool AAPointerInfoFloating::collectConstantsForGEP(Attributor &A,
                                                   const DataLayout &DL,
                                                   OffsetInfo &UsrOI,
                                                   const OffsetInfo &PtrOI,
                                                   const GEPOperator *GEP) {
  unsigned BitWidth = DL.getIndexTypeSizeInBits(GEP->getType());
  MapVector<Value *, APInt> VariableOffsets;
  APInt ConstantOffset(BitWidth, 0);
 
  assert(!UsrOI.isUnknown() && !PtrOI.isUnknown() &&
         "Don't look for constant values if the offset has already been "
         "determined to be unknown.");
 
  if (!GEP->collectOffset(DL, BitWidth, VariableOffsets, ConstantOffset)) {
    UsrOI.setUnknown();
    return true;
  }
 
  LLVM_DEBUG(dbgs() << "[AAPointerInfo] GEP offset is "
                    << (VariableOffsets.empty() ? "" : "not") << " constant "
                    << *GEP << "\n");
 
  auto Union = PtrOI;
  Union.addToAll(ConstantOffset.getSExtValue());
 
  // Each VI in VariableOffsets has a set of potential constant values. Every
  // combination of elements, picked one each from these sets, is separately
  // added to the original set of offsets, thus resulting in more offsets.
  for (const auto &VI : VariableOffsets) {
    auto *PotentialConstantsAA = A.getAAFor<AAPotentialConstantValues>(
        *this, IRPosition::value(*VI.first), DepClassTy::OPTIONAL);
    if (!PotentialConstantsAA || !PotentialConstantsAA->isValidState()) {
      UsrOI.setUnknown();
      return true;
    }
 
    // UndefValue is treated as a zero, which leaves Union as is.
    if (PotentialConstantsAA->undefIsContained())
      continue;
 
    // We need at least one constant in every set to compute an actual offset.
    // Otherwise, we end up pessimizing AAPointerInfo by respecting offsets that
    // don't actually exist. In other words, the absence of constant values
    // implies that the operation can be assumed dead for now.
    auto &AssumedSet = PotentialConstantsAA->getAssumedSet();
    if (AssumedSet.empty())
      return false;
 
    OffsetInfo Product;
    for (const auto &ConstOffset : AssumedSet) {
      auto CopyPerOffset = Union;
      CopyPerOffset.addToAll(ConstOffset.getSExtValue() *
                             VI.second.getZExtValue());
      Product.merge(CopyPerOffset);
    }
    Union = Product;
  }
 
  UsrOI = std::move(Union);
  return true;
}
 
ChangeStatus AAPointerInfoFloating::updateImpl(Attributor &A) {
  using namespace AA::PointerInfo;
  ChangeStatus Changed = ChangeStatus::UNCHANGED;
  const DataLayout &DL = A.getDataLayout();
  Value &AssociatedValue = getAssociatedValue();
 
  DenseMap<Value *, OffsetInfo> OffsetInfoMap;
  OffsetInfoMap[&AssociatedValue].insert(0);
 
  auto HandlePassthroughUser = [&](Value *Usr, Value *CurPtr, bool &Follow) {
    // One does not simply walk into a map and assign a reference to a possibly
    // new location. That can cause an invalidation before the assignment
    // happens, like so:
    //
    //   OffsetInfoMap[Usr] = OffsetInfoMap[CurPtr]; /* bad idea! */
    //
    // The RHS is a reference that may be invalidated by an insertion caused by
    // the LHS. So we ensure that the side-effect of the LHS happens first.
    auto &UsrOI = OffsetInfoMap[Usr];
    auto &PtrOI = OffsetInfoMap[CurPtr];
    assert(!PtrOI.isUnassigned() &&
           "Cannot pass through if the input Ptr was not visited!");
    UsrOI = PtrOI;
    Follow = true;
    return true;
  };
 
  const auto *F = getAnchorScope();
  const auto *CI =
      F ? A.getInfoCache().getAnalysisResultForFunction<CycleAnalysis>(*F)
        : nullptr;
  const auto *TLI =
      F ? A.getInfoCache().getTargetLibraryInfoForFunction(*F) : 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, 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.
      auto &UsrOI = OffsetInfoMap[Usr];
      auto &PtrOI = OffsetInfoMap[CurPtr];
 
      if (UsrOI.isUnknown())
        return true;
 
      if (PtrOI.isUnknown()) {
        Follow = true;
        UsrOI.setUnknown();
        return true;
      }
 
      Follow = collectConstantsForGEP(A, DL, UsrOI, PtrOI, GEP);
      return true;
    }
    if (isa<PtrToIntInst>(Usr))
      return false;
    if (isa<CastInst>(Usr) || isa<SelectInst>(Usr) || isa<ReturnInst>(Usr))
      return HandlePassthroughUser(Usr, 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.
      bool IsFirstPHIUser = !OffsetInfoMap.count(Usr);
      auto &UsrOI = OffsetInfoMap[Usr];
      auto &PtrOI = OffsetInfoMap[CurPtr];
 
      // Check if the PHI operand has already an unknown offset as we can't
      // improve on that anymore.
      if (PtrOI.isUnknown()) {
        LLVM_DEBUG(dbgs() << "[AAPointerInfo] PHI operand offset unknown "
                          << *CurPtr << " in " << *Usr << "\n");
        Follow = !UsrOI.isUnknown();
        UsrOI.setUnknown();
        return true;
      }
 
      // Check if the PHI is invariant (so far).
      if (UsrOI == PtrOI) {
        assert(!PtrOI.isUnassigned() &&
               "Cannot assign if the current Ptr was not visited!");
        LLVM_DEBUG(dbgs() << "[AAPointerInfo] PHI is invariant (so far)");
        return true;
      }
 
      // Check if the PHI operand can be traced back to AssociatedValue.
      APInt Offset(
          DL.getIndexSizeInBits(CurPtr->getType()->getPointerAddressSpace()),
          0);
      Value *CurPtrBase = CurPtr->stripAndAccumulateConstantOffsets(
          DL, Offset, /* AllowNonInbounds */ true);
      auto It = OffsetInfoMap.find(CurPtrBase);
      if (It == OffsetInfoMap.end()) {
        LLVM_DEBUG(dbgs() << "[AAPointerInfo] PHI operand is too complex "
                          << *CurPtr << " in " << *Usr << "\n");
        UsrOI.setUnknown();
        Follow = true;
        return true;
      }
 
      // Check if the PHI operand is not dependent on the PHI itself. Every
      // recurrence is a cyclic net of PHIs in the data flow, and has an
      // equivalent Cycle in the control flow. One of those PHIs must be in the
      // header of that control flow Cycle. This is independent of the choice of
      // Cycles reported by CycleInfo. It is sufficient to check the PHIs in
      // every Cycle header; if such a node is marked unknown, this will
      // eventually propagate through the whole net of PHIs in the recurrence.
      if (mayBeInCycle(CI, cast<Instruction>(Usr), /* HeaderOnly */ true)) {
        auto BaseOI = It->getSecond();
        BaseOI.addToAll(Offset.getZExtValue());
        if (IsFirstPHIUser || BaseOI == UsrOI) {
          LLVM_DEBUG(dbgs() << "[AAPointerInfo] PHI is invariant " << *CurPtr
                            << " in " << *Usr << "\n");
          return HandlePassthroughUser(Usr, CurPtr, Follow);
        }
 
        LLVM_DEBUG(
            dbgs() << "[AAPointerInfo] PHI operand pointer offset mismatch "
                   << *CurPtr << " in " << *Usr << "\n");
        UsrOI.setUnknown();
        Follow = true;
        return true;
      }
 
      UsrOI.merge(PtrOI);
      Follow = true;
      return true;
    }
 
    if (auto *LoadI = dyn_cast<LoadInst>(Usr)) {
      // If the access is to a pointer that may or may not be the associated
      // value, e.g. due to a PHI, we cannot assume it will be read.
      AccessKind AK = AccessKind::AK_R;
      if (getUnderlyingObject(CurPtr) == &AssociatedValue)
        AK = AccessKind(AK | AccessKind::AK_MUST);
      else
        AK = AccessKind(AK | AccessKind::AK_MAY);
      if (!handleAccess(A, *LoadI, /* Content */ nullptr, AK,
                        OffsetInfoMap[CurPtr].Offsets, Changed,
                        *LoadI->getType()))
        return false;
 
      auto IsAssumption = [](Instruction &I) {
        if (auto *II = dyn_cast<IntrinsicInst>(&I))
          return II->isAssumeLikeIntrinsic();
        return false;
      };
 
      auto IsImpactedInRange = [&](Instruction *FromI, Instruction *ToI) {
        // Check if the assumption and the load are executed together without
        // memory modification.
        do {
          if (FromI->mayWriteToMemory() && !IsAssumption(*FromI))
            return true;
          FromI = FromI->getNextNonDebugInstruction();
        } while (FromI && FromI != ToI);
        return false;
      };
 
      BasicBlock *BB = LoadI->getParent();
      auto IsValidAssume = [&](IntrinsicInst &IntrI) {
        if (IntrI.getIntrinsicID() != Intrinsic::assume)
          return false;
        BasicBlock *IntrBB = IntrI.getParent();
        if (IntrI.getParent() == BB) {
          if (IsImpactedInRange(LoadI->getNextNonDebugInstruction(), &IntrI))
            return false;
        } else {
          auto PredIt = pred_begin(IntrBB);
          if (PredIt == pred_end(IntrBB))
            return false;
          if ((*PredIt) != BB)
            return false;
          if (++PredIt != pred_end(IntrBB))
            return false;
          for (auto *SuccBB : successors(BB)) {
            if (SuccBB == IntrBB)
              continue;
            if (isa<UnreachableInst>(SuccBB->getTerminator()))
              continue;
            return false;
          }
          if (IsImpactedInRange(LoadI->getNextNonDebugInstruction(),
                                BB->getTerminator()))
            return false;
          if (IsImpactedInRange(&IntrBB->front(), &IntrI))
            return false;
        }
        return true;
      };
 
      std::pair<Value *, IntrinsicInst *> Assumption;
      for (const Use &LoadU : LoadI->uses()) {
        if (auto *CmpI = dyn_cast<CmpInst>(LoadU.getUser())) {
          if (!CmpI->isEquality() || !CmpI->isTrueWhenEqual())
            continue;
          for (const Use &CmpU : CmpI->uses()) {
            if (auto *IntrI = dyn_cast<IntrinsicInst>(CmpU.getUser())) {
              if (!IsValidAssume(*IntrI))
                continue;
              int Idx = CmpI->getOperandUse(0) == LoadU;
              Assumption = {CmpI->getOperand(Idx), IntrI};
              break;
            }
          }
        }
        if (Assumption.first)
          break;
      }
 
      // Check if we found an assumption associated with this load.
      if (!Assumption.first || !Assumption.second)
        return true;
 
      LLVM_DEBUG(dbgs() << "[AAPointerInfo] Assumption found "
                        << *Assumption.second << ": " << *LoadI
                        << " == " << *Assumption.first << "\n");
      bool UsedAssumedInformation = false;
      std::optional<Value *> Content = nullptr;
      if (Assumption.first)
        Content =
            A.getAssumedSimplified(*Assumption.first, *this,
                                   UsedAssumedInformation, AA::Interprocedural);
      return handleAccess(
          A, *Assumption.second, Content, AccessKind::AK_ASSUMPTION,
          OffsetInfoMap[CurPtr].Offsets, Changed, *LoadI->getType());
    }
 
    auto HandleStoreLike = [&](Instruction &I, Value *ValueOp, Type &ValueTy,
                               ArrayRef<Value *> OtherOps, AccessKind AK) {
      for (auto *OtherOp : OtherOps) {
        if (OtherOp == CurPtr) {
          LLVM_DEBUG(
              dbgs()
              << "[AAPointerInfo] Escaping use in store like instruction " << I
              << "\n");
          return false;
        }
      }
 
      // If the access is to a pointer that may or may not be the associated
      // value, e.g. due to a PHI, we cannot assume it will be written.
      if (getUnderlyingObject(CurPtr) == &AssociatedValue)
        AK = AccessKind(AK | AccessKind::AK_MUST);
      else
        AK = AccessKind(AK | AccessKind::AK_MAY);
      bool UsedAssumedInformation = false;
      std::optional<Value *> Content = nullptr;
      if (ValueOp)
        Content = A.getAssumedSimplified(
            *ValueOp, *this, UsedAssumedInformation, AA::Interprocedural);
      return handleAccess(A, I, Content, AK, OffsetInfoMap[CurPtr].Offsets,
                          Changed, ValueTy);
    };
 
    if (auto *StoreI = dyn_cast<StoreInst>(Usr))
      return HandleStoreLike(*StoreI, StoreI->getValueOperand(),
                             *StoreI->getValueOperand()->getType(),
                             {StoreI->getValueOperand()}, AccessKind::AK_W);
    if (auto *RMWI = dyn_cast<AtomicRMWInst>(Usr))
      return HandleStoreLike(*RMWI, nullptr, *RMWI->getValOperand()->getType(),
                             {RMWI->getValOperand()}, AccessKind::AK_RW);
    if (auto *CXI = dyn_cast<AtomicCmpXchgInst>(Usr))
      return HandleStoreLike(
          *CXI, nullptr, *CXI->getNewValOperand()->getType(),
          {CXI->getCompareOperand(), CXI->getNewValOperand()},
          AccessKind::AK_RW);
 
    if (auto *CB = dyn_cast<CallBase>(Usr)) {
      if (CB->isLifetimeStartOrEnd())
        return true;
      if (getFreedOperand(CB, TLI) == U)
        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);
        if (!CSArgPI)
          return false;
        Changed =
            translateAndAddState(A, *CSArgPI, OffsetInfoMap[CurPtr], *CB) |
            Changed;
        return isValidState();
      }
      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) {
    assert(OffsetInfoMap.count(OldU) && "Old use should be known already!");
    if (OffsetInfoMap.count(NewU)) {
      LLVM_DEBUG({
        if (!(OffsetInfoMap[NewU] == OffsetInfoMap[OldU])) {
          dbgs() << "[AAPointerInfo] Equivalent use callback failed: "
                 << OffsetInfoMap[NewU] << " vs " << OffsetInfoMap[OldU]
                 << "\n";
        }
      });
      return OffsetInfoMap[NewU] == OffsetInfoMap[OldU];
    }
    OffsetInfoMap[NewU] = OffsetInfoMap[OldU];
    return true;
  };
  if (!A.checkForAllUses(UsePred, *this, AssociatedValue,
                         /* CheckBBLivenessOnly */ true, DepClassTy::OPTIONAL,
                         /* IgnoreDroppableUses */ true, EquivalentUseCB)) {
    LLVM_DEBUG(dbgs() << "[AAPointerInfo] Check for all uses failed, abort!\n");
    return indicatePessimisticFixpoint();
  }
 
  LLVM_DEBUG({
    dbgs() << "Accesses by bin after update:\n";
    dumpState(dbgs());
  });
 
  return Changed;
}
 
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::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 = AA::RangeTy::Unknown;
      if (Length)
        LengthVal = Length->getSExtValue();
      unsigned ArgNo = getIRPosition().getCallSiteArgNo();
      ChangeStatus Changed = ChangeStatus::UNCHANGED;
      if (ArgNo > 1) {
        LLVM_DEBUG(dbgs() << "[AAPointerInfo] Unhandled memory intrinsic "
                          << *MI << "\n");
        return indicatePessimisticFixpoint();
      } else {
        auto Kind =
            ArgNo == 0 ? AccessKind::AK_MUST_WRITE : AccessKind::AK_MUST_READ;
        Changed =
            Changed | addAccess(A, {0, LengthVal}, *MI, nullptr, Kind, nullptr);
      }
      LLVM_DEBUG({
        dbgs() << "Accesses by bin after update:\n";
        dumpState(dbgs());
      });
 
      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) {
      const IRPosition &ArgPos = IRPosition::argument(*Arg);
      auto *ArgAA =
          A.getAAFor<AAPointerInfo>(*this, ArgPos, DepClassTy::REQUIRED);
      if (ArgAA && ArgAA->getState().isValidState())
        return translateAndAddStateFromCallee(A, *ArgAA,
                                              *cast<CallBase>(getCtxI()));
      if (!Arg->getParent()->isDeclaration())
        return indicatePessimisticFixpoint();
    }
 
    bool IsKnownNoCapture;
    if (!AA::hasAssumedIRAttr<Attribute::NoCapture>(
            A, this, getIRPosition(), DepClassTy::OPTIONAL, IsKnownNoCapture))
      return indicatePessimisticFixpoint();
 
    bool IsKnown = false;
    if (AA::isAssumedReadNone(A, getIRPosition(), *this, IsKnown))
      return ChangeStatus::UNCHANGED;
    bool ReadOnly = AA::isAssumedReadOnly(A, getIRPosition(), *this, IsKnown);
    auto Kind =
        ReadOnly ? AccessKind::AK_MAY_READ : AccessKind::AK_MAY_READ_WRITE;
    return addAccess(A, AA::RangeTy::getUnknown(), *getCtxI(), nullptr, Kind,
                     nullptr);
  }
 
  /// 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) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    bool IsKnown;
    assert(!AA::hasAssumedIRAttr<Attribute::NoUnwind>(
        A, nullptr, getIRPosition(), DepClassTy::NONE, IsKnown));
    (void)IsKnown;
  }
 
  const std::string getAsStr(Attributor *A) 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(/* IncludePhaseOneUnwind */ true))
        return true;
 
      if (const auto *CB = dyn_cast<CallBase>(&I)) {
        bool IsKnownNoUnwind;
        return AA::hasAssumedIRAttr<Attribute::NoUnwind>(
            A, this, IRPosition::callsite_function(*CB), DepClassTy::REQUIRED,
            IsKnownNoUnwind);
      }
      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
    : AACalleeToCallSite<AANoUnwind, AANoUnwindImpl> {
  AANoUnwindCallSite(const IRPosition &IRP, Attributor &A)
      : AACalleeToCallSite<AANoUnwind, AANoUnwindImpl>(IRP, A) {}
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(nounwind); }
};
} // namespace
 
/// ------------------------ NoSync Function Attribute -------------------------
 
bool AANoSync::isAlignedBarrier(const CallBase &CB, bool ExecutedAligned) {
  switch (CB.getIntrinsicID()) {
  case Intrinsic::nvvm_barrier0:
  case Intrinsic::nvvm_barrier0_and:
  case Intrinsic::nvvm_barrier0_or:
  case Intrinsic::nvvm_barrier0_popc:
    return true;
  case Intrinsic::amdgcn_s_barrier:
    if (ExecutedAligned)
      return true;
    break;
  default:
    break;
  }
  return hasAssumption(CB, KnownAssumptionString("ompx_aligned_barrier"));
}
 
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) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    bool IsKnown;
    assert(!AA::hasAssumedIRAttr<Attribute::NoSync>(A, nullptr, getIRPosition(),
                                                    DepClassTy::NONE, IsKnown));
    (void)IsKnown;
  }
 
  const std::string getAsStr(Attributor *A) 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;
 
    bool IsKnown;
    CallBase &CB = cast<CallBase>(I);
    if (AA::hasAssumedIRAttr<Attribute::NoSync>(
            A, this, IRPosition::callsite_function(CB), DepClassTy::OPTIONAL,
            IsKnown))
      return true;
 
    // non-convergent and readnone imply nosync.
    return !CB.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 : AACalleeToCallSite<AANoSync, AANoSyncImpl> {
  AANoSyncCallSite(const IRPosition &IRP, Attributor &A)
      : AACalleeToCallSite<AANoSync, AANoSyncImpl>(IRP, A) {}
 
  /// 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::initialize(...).
  void initialize(Attributor &A) override {
    bool IsKnown;
    assert(!AA::hasAssumedIRAttr<Attribute::NoFree>(A, nullptr, getIRPosition(),
                                                    DepClassTy::NONE, IsKnown));
    (void)IsKnown;
  }
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    auto CheckForNoFree = [&](Instruction &I) {
      bool IsKnown;
      return AA::hasAssumedIRAttr<Attribute::NoFree>(
          A, this, IRPosition::callsite_function(cast<CallBase>(I)),
          DepClassTy::REQUIRED, IsKnown);
    };
 
    bool UsedAssumedInformation = false;
    if (!A.checkForAllCallLikeInstructions(CheckForNoFree, *this,
                                           UsedAssumedInformation))
      return indicatePessimisticFixpoint();
    return ChangeStatus::UNCHANGED;
  }
 
  /// See AbstractAttribute::getAsStr().
  const std::string getAsStr(Attributor *A) 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 : AACalleeToCallSite<AANoFree, AANoFreeImpl> {
  AANoFreeCallSite(const IRPosition &IRP, Attributor &A)
      : AACalleeToCallSite<AANoFree, AANoFreeImpl>(IRP, A) {}
 
  /// 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();
 
    bool IsKnown;
    if (AA::hasAssumedIRAttr<Attribute::NoFree>(A, this,
                                                IRPosition::function_scope(IRP),
                                                DepClassTy::OPTIONAL, IsKnown))
      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);
 
        bool IsKnown;
        return AA::hasAssumedIRAttr<Attribute::NoFree>(
            A, this, IRPosition::callsite_argument(*CB, ArgNo),
            DepClassTy::REQUIRED, IsKnown);
      }
 
      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);
    bool IsKnown;
    if (AA::hasAssumedIRAttr<Attribute::NoFree>(A, this, ArgPos,
                                                DepClassTy::REQUIRED, IsKnown))
      return ChangeStatus::UNCHANGED;
    return indicatePessimisticFixpoint();
  }
 
  /// 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 ------------------------
 
bool AANonNull::isImpliedByIR(Attributor &A, const IRPosition &IRP,
                              Attribute::AttrKind ImpliedAttributeKind,
                              bool IgnoreSubsumingPositions) {
  SmallVector<Attribute::AttrKind, 2> AttrKinds;
  AttrKinds.push_back(Attribute::NonNull);
  if (!NullPointerIsDefined(IRP.getAnchorScope(),
                            IRP.getAssociatedType()->getPointerAddressSpace()))
    AttrKinds.push_back(Attribute::Dereferenceable);
  if (A.hasAttr(IRP, AttrKinds, IgnoreSubsumingPositions, Attribute::NonNull))
    return true;
 
  DominatorTree *DT = nullptr;
  AssumptionCache *AC = nullptr;
  InformationCache &InfoCache = A.getInfoCache();
  if (const Function *Fn = IRP.getAnchorScope()) {
    if (!Fn->isDeclaration()) {
      DT = InfoCache.getAnalysisResultForFunction<DominatorTreeAnalysis>(*Fn);
      AC = InfoCache.getAnalysisResultForFunction<AssumptionAnalysis>(*Fn);
    }
  }
 
  SmallVector<AA::ValueAndContext> Worklist;
  if (IRP.getPositionKind() != IRP_RETURNED) {
    Worklist.push_back({IRP.getAssociatedValue(), IRP.getCtxI()});
  } else {
    bool UsedAssumedInformation = false;
    if (!A.checkForAllInstructions(
            [&](Instruction &I) {
              Worklist.push_back({*cast<ReturnInst>(I).getReturnValue(), &I});
              return true;
            },
            IRP.getAssociatedFunction(), nullptr, {Instruction::Ret},
            UsedAssumedInformation))
      return false;
  }
 
  if (llvm::any_of(Worklist, [&](AA::ValueAndContext VAC) {
        return !isKnownNonZero(VAC.getValue(), A.getDataLayout(), 0, AC,
                               VAC.getCtxI(), DT);
      }))
    return false;
 
  A.manifestAttrs(IRP, {Attribute::get(IRP.getAnchorValue().getContext(),
                                       Attribute::NonNull)});
  return true;
}
 
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.
    bool IsKnownNonNull;
    AA::hasAssumedIRAttr<Attribute::NonNull>(A, &QueryingAA, IRP,
                                             DepClassTy::NONE, IsKnownNonNull);
    IsNonNull |= IsKnownNonNull;
    auto *DerefAA =
        A.getAAFor<AADereferenceable>(QueryingAA, IRP, DepClassTy::NONE);
    return DerefAA ? DerefAA->getKnownDereferenceableBytes() : 0;
  }
 
  std::optional<MemoryLocation> Loc = MemoryLocation::getOrNone(I);
  if (!Loc || Loc->Ptr != UseV || !Loc->Size.isPrecise() ||
      Loc->Size.isScalable() || 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) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    Value &V = *getAssociatedValue().stripPointerCasts();
    if (isa<ConstantPointerNull>(V)) {
      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(Attributor *A) const override {
    return getAssumed() ? "nonnull" : "may-null";
  }
};
 
/// 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 {
    auto CheckIRP = [&](const IRPosition &IRP) {
      bool IsKnownNonNull;
      return AA::hasAssumedIRAttr<Attribute::NonNull>(
          A, *this, IRP, DepClassTy::OPTIONAL, IsKnownNonNull);
    };
 
    bool Stripped;
    bool UsedAssumedInformation = false;
    Value *AssociatedValue = &getAssociatedValue();
    SmallVector<AA::ValueAndContext> Values;
    if (!A.getAssumedSimplifiedValues(getIRPosition(), *this, Values,
                                      AA::AnyScope, UsedAssumedInformation))
      Stripped = false;
    else
      Stripped =
          Values.size() != 1 || Values.front().getValue() != AssociatedValue;
 
    if (!Stripped) {
      bool IsKnown;
      if (auto *PHI = dyn_cast<PHINode>(AssociatedValue))
        if (llvm::all_of(PHI->incoming_values(), [&](Value *Op) {
              return AA::hasAssumedIRAttr<Attribute::NonNull>(
                  A, this, IRPosition::value(*Op), DepClassTy::OPTIONAL,
                  IsKnown);
            }))
          return ChangeStatus::UNCHANGED;
      if (auto *Select = dyn_cast<SelectInst>(AssociatedValue))
        if (AA::hasAssumedIRAttr<Attribute::NonNull>(
                A, this, IRPosition::value(*Select->getFalseValue()),
                DepClassTy::OPTIONAL, IsKnown) &&
            AA::hasAssumedIRAttr<Attribute::NonNull>(
                A, this, IRPosition::value(*Select->getTrueValue()),
                DepClassTy::OPTIONAL, IsKnown))
          return ChangeStatus::UNCHANGED;
 
      // If we haven't stripped anything we might still be able to use a
      // different AA, but only if the IRP changes. Effectively when we
      // interpret this not as a call site value but as a floating/argument
      // value.
      const IRPosition AVIRP = IRPosition::value(*AssociatedValue);
      if (AVIRP == getIRPosition() || !CheckIRP(AVIRP))
        return indicatePessimisticFixpoint();
      return ChangeStatus::UNCHANGED;
    }
 
    for (const auto &VAC : Values)
      if (!CheckIRP(IRPosition::value(*VAC.getValue())))
        return indicatePessimisticFixpoint();
 
    return ChangeStatus::UNCHANGED;
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(nonnull) }
};
 
/// NonNull attribute for function return value.
struct AANonNullReturned final
    : AAReturnedFromReturnedValues<AANonNull, AANonNull, AANonNull::StateType,
                                   false, AANonNull::IRAttributeKind, false> {
  AANonNullReturned(const IRPosition &IRP, Attributor &A)
      : AAReturnedFromReturnedValues<AANonNull, AANonNull, AANonNull::StateType,
                                     false, Attribute::NonNull, false>(IRP, A) {
  }
 
  /// See AbstractAttribute::getAsStr().
  const std::string getAsStr(Attributor *A) 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
    : AACalleeToCallSite<AANonNull, AANonNullImpl> {
  AANonNullCallSiteReturned(const IRPosition &IRP, Attributor &A)
      : AACalleeToCallSite<AANonNull, AANonNullImpl>(IRP, A) {}
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(nonnull) }
};
} // namespace
 
/// ------------------------ Must-Progress Attributes --------------------------
namespace {
struct AAMustProgressImpl : public AAMustProgress {
  AAMustProgressImpl(const IRPosition &IRP, Attributor &A)
      : AAMustProgress(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    bool IsKnown;
    assert(!AA::hasAssumedIRAttr<Attribute::MustProgress>(
        A, nullptr, getIRPosition(), DepClassTy::NONE, IsKnown));
    (void)IsKnown;
  }
 
  /// See AbstractAttribute::getAsStr()
  const std::string getAsStr(Attributor *A) const override {
    return getAssumed() ? "mustprogress" : "may-not-progress";
  }
};
 
struct AAMustProgressFunction final : AAMustProgressImpl {
  AAMustProgressFunction(const IRPosition &IRP, Attributor &A)
      : AAMustProgressImpl(IRP, A) {}
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    bool IsKnown;
    if (AA::hasAssumedIRAttr<Attribute::WillReturn>(
            A, this, getIRPosition(), DepClassTy::OPTIONAL, IsKnown)) {
      if (IsKnown)
        return indicateOptimisticFixpoint();
      return ChangeStatus::UNCHANGED;
    }
 
    auto CheckForMustProgress = [&](AbstractCallSite ACS) {
      IRPosition IPos = IRPosition::callsite_function(*ACS.getInstruction());
      bool IsKnownMustProgress;
      return AA::hasAssumedIRAttr<Attribute::MustProgress>(
          A, this, IPos, DepClassTy::REQUIRED, IsKnownMustProgress,
          /* IgnoreSubsumingPositions */ true);
    };
 
    bool AllCallSitesKnown = true;
    if (!A.checkForAllCallSites(CheckForMustProgress, *this,
                                /* RequireAllCallSites */ true,
                                AllCallSitesKnown))
      return indicatePessimisticFixpoint();
 
    return ChangeStatus::UNCHANGED;
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override {
    STATS_DECLTRACK_FN_ATTR(mustprogress)
  }
};
 
/// MustProgress attribute deduction for a call sites.
struct AAMustProgressCallSite final : AAMustProgressImpl {
  AAMustProgressCallSite(const IRPosition &IRP, Attributor &A)
      : AAMustProgressImpl(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.
    const IRPosition &FnPos = IRPosition::function(*getAnchorScope());
    bool IsKnownMustProgress;
    if (!AA::hasAssumedIRAttr<Attribute::MustProgress>(
            A, this, FnPos, DepClassTy::REQUIRED, IsKnownMustProgress))
      return indicatePessimisticFixpoint();
    return ChangeStatus::UNCHANGED;
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override {
    STATS_DECLTRACK_CS_ATTR(mustprogress);
  }
};
} // namespace
 
/// ------------------------ No-Recurse Attributes ----------------------------
 
namespace {
struct AANoRecurseImpl : public AANoRecurse {
  AANoRecurseImpl(const IRPosition &IRP, Attributor &A) : AANoRecurse(IRP, A) {}
 
  /// See AbstractAttribute::initialize(...).
  void initialize(Attributor &A) override {
    bool IsKnown;
    assert(!AA::hasAssumedIRAttr<Attribute::NoRecurse>(
        A, nullptr, getIRPosition(), DepClassTy::NONE, IsKnown));
    (void)IsKnown;
  }
 
  /// See AbstractAttribute::getAsStr()
  const std::string getAsStr(Attributor *A) 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) {
      bool IsKnownNoRecurse;
      if (!AA::hasAssumedIRAttr<Attribute::NoRecurse>(
              A, this,
              IRPosition::function(*ACS.getInstruction()->getFunction()),
              DepClassTy::NONE, IsKnownNoRecurse))
        return false;
      return 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 AAInterFnReachability *EdgeReachability =
        A.getAAFor<AAInterFnReachability>(*this, getIRPosition(),
                                          DepClassTy::REQUIRED);
    if (EdgeReachability && 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
    : AACalleeToCallSite<AANoRecurse, AANoRecurseImpl> {
  AANoRecurseCallSite(const IRPosition &IRP, Attributor &A)
      : AACalleeToCallSite<AANoRecurse, AANoRecurseImpl>(IRP, A) {}
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(norecurse); }
};
} // namespace
 
/// ------------------------ No-Convergent Attribute --------------------------
 
namespace {
struct AANonConvergentImpl : public AANonConvergent {
  AANonConvergentImpl(const IRPosition &IRP, Attributor &A)
      : AANonConvergent(IRP, A) {}
 
  /// See AbstractAttribute::getAsStr()
  const std::string getAsStr(Attributor *A) const override {
    return getAssumed() ? "non-convergent" : "may-be-convergent";
  }
};
 
struct AANonConvergentFunction final : AANonConvergentImpl {
  AANonConvergentFunction(const IRPosition &IRP, Attributor &A)
      : AANonConvergentImpl(IRP, A) {}
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    // If all function calls are known to not be convergent, we are not
    // convergent.
    auto CalleeIsNotConvergent = [&](Instruction &Inst) {
      CallBase &CB = cast<CallBase>(Inst);
      auto *Callee = dyn_cast_if_present<Function>(CB.getCalledOperand());
      if (!Callee || Callee->isIntrinsic()) {
        return false;
      }
      if (Callee->isDeclaration()) {
        return !Callee->hasFnAttribute(Attribute::Convergent);
      }
      const auto *ConvergentAA = A.getAAFor<AANonConvergent>(
          *this, IRPosition::function(*Callee), DepClassTy::REQUIRED);
      return ConvergentAA && ConvergentAA->isAssumedNotConvergent();
    };
 
    bool UsedAssumedInformation = false;
    if (!A.checkForAllCallLikeInstructions(CalleeIsNotConvergent, *this,
                                           UsedAssumedInformation)) {
      return indicatePessimisticFixpoint();
    }
    return ChangeStatus::UNCHANGED;
  }
 
  ChangeStatus manifest(Attributor &A) override {
    if (isKnownNotConvergent() &&
        A.hasAttr(getIRPosition(), Attribute::Convergent)) {
      A.removeAttrs(getIRPosition(), {Attribute::Convergent});
      return ChangeStatus::CHANGED;
    }
    return ChangeStatus::UNCHANGED;
  }
 
  void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(convergent) }
};
} // 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.
      std::optional<Value *> SimplifiedPtrOp =
          stopOnUndefOrAssumed(A, PtrOp, &I);
      if (!SimplifiedPtrOp || !*SimplifiedPtrOp)
        return true;
      const Value *PtrOpVal = *SimplifiedPtrOp;
 
      // 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.
      std::optional<Value *> SimplifiedCond =
          stopOnUndefOrAssumed(A, BrInst->getCondition(), BrInst);
      if (!SimplifiedCond || !*SimplifiedCond)
        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);
      auto *Callee = dyn_cast_if_present<Function>(CB.getCalledOperand());
      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);
        bool IsKnownNoUndef;
        AA::hasAssumedIRAttr<Attribute::NoUndef>(
            A, this, CalleeArgumentIRP, DepClassTy::NONE, IsKnownNoUndef);
        if (!IsKnownNoUndef)
          continue;
        bool UsedAssumedInformation = false;
        std::optional<Value *> SimplifiedVal =
            A.getAssumedSimplified(IRPosition::value(*ArgVal), *this,
                                   UsedAssumedInformation, AA::Interprocedural);
        if (UsedAssumedInformation)
          continue;
        if (SimplifiedVal && !*SimplifiedVal)
          return true;
        if (!SimplifiedVal || isa<UndefValue>(**SimplifiedVal)) {
          KnownUBInsts.insert(&I);
          continue;
        }
        if (!ArgVal->getType()->isPointerTy() ||
            !isa<ConstantPointerNull>(**SimplifiedVal))
          continue;
        bool IsKnownNonNull;
        AA::hasAssumedIRAttr<Attribute::NonNull>(
            A, this, CalleeArgumentIRP, DepClassTy::NONE, IsKnownNonNull);
        if (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.
      std::optional<Value *> SimplifiedRetValue =
          stopOnUndefOrAssumed(A, RI.getReturnValue(), &I);
      if (!SimplifiedRetValue || !*SimplifiedRetValue)
        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)) {
        bool IsKnownNonNull;
        AA::hasAssumedIRAttr<Attribute::NonNull>(
            A, this, IRPosition::returned(*getAnchorScope()), DepClassTy::NONE,
            IsKnownNonNull);
        if (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)) {
        bool IsKnownNoUndef;
        AA::hasAssumedIRAttr<Attribute::NoUndef>(
            A, this, ReturnIRP, DepClassTy::NONE, IsKnownNoUndef);
        if (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(Attributor *A) 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 std::nullopt 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.
  std::optional<Value *> stopOnUndefOrAssumed(Attributor &A, Value *V,
                                              Instruction *I) {
    bool UsedAssumedInformation = false;
    std::optional<Value *> SimplifiedV =
        A.getAssumedSimplified(IRPosition::value(*V), *this,
                               UsedAssumedInformation, AA::Interprocedural);
    if (!UsedAssumedInformation) {
      // Don't depend on assumed values.
      if (!SimplifiedV) {
        // 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 std::nullopt;
      }
      if (!*SimplifiedV)
        return nullptr;
      V = *SimplifiedV;
    }
    if (isa<UndefValue>(V)) {
      KnownUBInsts.insert(I);
      return std::nullopt;
    }
    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 {
    bool IsKnown;
    assert(!AA::hasAssumedIRAttr<Attribute::WillReturn>(
        A, nullptr, getIRPosition(), DepClassTy::NONE, IsKnown));
    (void)IsKnown;
  }
 
  /// Check for `mustprogress` and `readonly` as they imply `willreturn`.
  bool isImpliedByMustprogressAndReadonly(Attributor &A, bool KnownOnly) {
    if (!A.hasAttr(getIRPosition(), {Attribute::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));
      bool IsKnown;
      if (AA::hasAssumedIRAttr<Attribute::WillReturn>(
              A, this, IPos, DepClassTy::REQUIRED, IsKnown)) {
        if (IsKnown)
          return true;
      } else {
        return false;
      }
      bool IsKnownNoRecurse;
      return AA::hasAssumedIRAttr<Attribute::NoRecurse>(
          A, this, IPos, DepClassTy::REQUIRED, IsKnownNoRecurse);
    };
 
    bool UsedAssumedInformation = false;
    if (!A.checkForAllCallLikeInstructions(CheckForWillReturn, *this,
                                           UsedAssumedInformation))
      return indicatePessimisticFixpoint();
 
    return ChangeStatus::UNCHANGED;
  }
 
  /// See AbstractAttribute::getAsStr()
  const std::string getAsStr(Attributor *A) 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();
    assert(F && "Did expect an anchor function");
    if (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
    : AACalleeToCallSite<AAWillReturn, AAWillReturnImpl> {
  AAWillReturnCallSite(const IRPosition &IRP, Attributor &A)
      : AACalleeToCallSite<AAWillReturn, AAWillReturnImpl>(IRP, A) {}
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    if (isImpliedByMustprogressAndReadonly(A, /* KnownOnly */ false))
      return ChangeStatus::UNCHANGED;
 
    return AACalleeToCallSite::updateImpl(A);
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(willreturn); }
};
} // namespace
 
/// -------------------AAIntraFnReachability Attribute--------------------------
 
/// All information associated with a reachability query. This boilerplate code
/// is used by both AAIntraFnReachability and AAInterFnReachability, with
/// different \p ToTy values.
template <typename ToTy> struct ReachabilityQueryInfo {
  enum class Reachable {
    No,
    Yes,
  };
 
  /// Start here,
  const Instruction *From = nullptr;
  /// reach this place,
  const ToTy *To = nullptr;
  /// without going through any of these instructions,
  const AA::InstExclusionSetTy *ExclusionSet = nullptr;
  /// and remember if it worked:
  Reachable Result = Reachable::No;
 
  /// Precomputed hash for this RQI.
  unsigned Hash = 0;
 
  unsigned computeHashValue() const {
    assert(Hash == 0 && "Computed hash twice!");
    using InstSetDMI = DenseMapInfo<const AA::InstExclusionSetTy *>;
    using PairDMI = DenseMapInfo<std::pair<const Instruction *, const ToTy *>>;
    return const_cast<ReachabilityQueryInfo<ToTy> *>(this)->Hash =
               detail::combineHashValue(PairDMI ::getHashValue({From, To}),
                                        InstSetDMI::getHashValue(ExclusionSet));
  }
 
  ReachabilityQueryInfo(const Instruction *From, const ToTy *To)
      : From(From), To(To) {}
 
  /// Constructor replacement to ensure unique and stable sets are used for the
  /// cache.
  ReachabilityQueryInfo(Attributor &A, const Instruction &From, const ToTy &To,
                        const AA::InstExclusionSetTy *ES, bool MakeUnique)
      : From(&From), To(&To), ExclusionSet(ES) {
 
    if (!ES || ES->empty()) {
      ExclusionSet = nullptr;
    } else if (MakeUnique) {
      ExclusionSet = A.getInfoCache().getOrCreateUniqueBlockExecutionSet(ES);
    }
  }
 
  ReachabilityQueryInfo(const ReachabilityQueryInfo &RQI)
      : From(RQI.From), To(RQI.To), ExclusionSet(RQI.ExclusionSet) {}
};
 
namespace llvm {
template <typename ToTy> struct DenseMapInfo<ReachabilityQueryInfo<ToTy> *> {
  using InstSetDMI = DenseMapInfo<const AA::InstExclusionSetTy *>;
  using PairDMI = DenseMapInfo<std::pair<const Instruction *, const ToTy *>>;
 
  static ReachabilityQueryInfo<ToTy> EmptyKey;
  static ReachabilityQueryInfo<ToTy> TombstoneKey;
 
  static inline ReachabilityQueryInfo<ToTy> *getEmptyKey() { return &EmptyKey; }
  static inline ReachabilityQueryInfo<ToTy> *getTombstoneKey() {
    return &TombstoneKey;
  }
  static unsigned getHashValue(const ReachabilityQueryInfo<ToTy> *RQI) {
    return RQI->Hash ? RQI->Hash : RQI->computeHashValue();
  }
  static bool isEqual(const ReachabilityQueryInfo<ToTy> *LHS,
                      const ReachabilityQueryInfo<ToTy> *RHS) {
    if (!PairDMI::isEqual({LHS->From, LHS->To}, {RHS->From, RHS->To}))
      return false;
    return InstSetDMI::isEqual(LHS->ExclusionSet, RHS->ExclusionSet);
  }
};
 
#define DefineKeys(ToTy)                                                       \
  template <>                                                                  \
  ReachabilityQueryInfo<ToTy>                                                  \
      DenseMapInfo<ReachabilityQueryInfo<ToTy> *>::EmptyKey =                  \
          ReachabilityQueryInfo<ToTy>(                                         \
              DenseMapInfo<const Instruction *>::getEmptyKey(),                \
              DenseMapInfo<const ToTy *>::getEmptyKey());                      \
  template <>                                                                  \
  ReachabilityQueryInfo<ToTy>                                                  \
      DenseMapInfo<ReachabilityQueryInfo<ToTy> *>::TombstoneKey =              \
          ReachabilityQueryInfo<ToTy>(                                         \
              DenseMapInfo<const Instruction *>::getTombstoneKey(),            \
              DenseMapInfo<const ToTy *>::getTombstoneKey());
 
DefineKeys(Instruction) DefineKeys(Function)
#undef DefineKeys
 
} // namespace llvm
 
namespace {
 
template <typename BaseTy, typename ToTy>
struct CachedReachabilityAA : public BaseTy {
  using RQITy = ReachabilityQueryInfo<ToTy>;
 
  CachedReachabilityAA(const IRPosition &IRP, Attributor &A) : BaseTy(IRP, A) {}
 
  /// See AbstractAttribute::isQueryAA.
  bool isQueryAA() const override { return true; }
 
  /// See AbstractAttribute::updateImpl(...).
  ChangeStatus updateImpl(Attributor &A) override {
    ChangeStatus Changed = ChangeStatus::UNCHANGED;
    for (unsigned u = 0, e = QueryVector.size(); u < e; ++u) {
      RQITy *RQI = QueryVector[u];
      if (RQI->Result == RQITy::Reachable::No &&
          isReachableImpl(A, *RQI, /*IsTemporaryRQI=*/false))
        Changed = ChangeStatus::CHANGED;
    }
    return Changed;
  }
 
  virtual bool isReachableImpl(Attributor &A, RQITy &RQI,
                               bool IsTemporaryRQI) = 0;
 
  bool rememberResult(Attributor &A, typename RQITy::Reachable Result,
                      RQITy &RQI, bool UsedExclusionSet, bool IsTemporaryRQI) {
    RQI.Result = Result;
 
    // Remove the temporary RQI from the cache.
    if (IsTemporaryRQI)
      QueryCache.erase(&RQI);
 
    // Insert a plain RQI (w/o exclusion set) if that makes sense. Two options:
    // 1) If it is reachable, it doesn't matter if we have an exclusion set for
    // this query. 2) We did not use the exclusion set, potentially because
    // there is none.
    if (Result == RQITy::Reachable::Yes || !UsedExclusionSet) {
      RQITy PlainRQI(RQI.From, RQI.To);
      if (!QueryCache.count(&PlainRQI)) {
        RQITy *RQIPtr = new (A.Allocator) RQITy(RQI.From, RQI.To);
        RQIPtr->Result = Result;
        QueryVector.push_back(RQIPtr);
        QueryCache.insert(RQIPtr);
      }
    }
 
    // Check if we need to insert a new permanent RQI with the exclusion set.
    if (IsTemporaryRQI && Result != RQITy::Reachable::Yes && UsedExclusionSet) {
      assert((!RQI.ExclusionSet || !RQI.ExclusionSet->empty()) &&
             "Did not expect empty set!");
      RQITy *RQIPtr = new (A.Allocator)
          RQITy(A, *RQI.From, *RQI.To, RQI.ExclusionSet, true);
      assert(RQIPtr->Result == RQITy::Reachable::No && "Already reachable?");
      RQIPtr->Result = Result;
      assert(!QueryCache.count(RQIPtr));
      QueryVector.push_back(RQIPtr);
      QueryCache.insert(RQIPtr);
    }
 
    if (Result == RQITy::Reachable::No && IsTemporaryRQI)
      A.registerForUpdate(*this);
    return Result == RQITy::Reachable::Yes;
  }
 
  const std::string getAsStr(Attributor *A) const override {
    // TODO: Return the number of reachable queries.
    return "#queries(" + std::to_string(QueryVector.size()) + ")";
  }
 
  bool checkQueryCache(Attributor &A, RQITy &StackRQI,
                       typename RQITy::Reachable &Result) {
    if (!this->getState().isValidState()) {
      Result = RQITy::Reachable::Yes;
      return true;
    }
 
    // If we have an exclusion set we might be able to find our answer by
    // ignoring it first.
    if (StackRQI.ExclusionSet) {
      RQITy PlainRQI(StackRQI.From, StackRQI.To);
      auto It = QueryCache.find(&PlainRQI);
      if (It != QueryCache.end() && (*It)->Result == RQITy::Reachable::No) {
        Result = RQITy::Reachable::No;
        return true;
      }
    }
 
    auto It = QueryCache.find(&StackRQI);
    if (It != QueryCache.end()) {
      Result = (*It)->Result;
      return true;
    }
 
    // Insert a temporary for recursive queries. We will replace it with a
    // permanent entry later.
    QueryCache.insert(&StackRQI);
    return false;
  }
 
private:
  SmallVector<RQITy *> QueryVector;
  DenseSet<RQITy *> QueryCache;
};
 
struct AAIntraFnReachabilityFunction final
    : public CachedReachabilityAA<AAIntraFnReachability, Instruction> {
  using Base = CachedReachabilityAA<AAIntraFnReachability, Instruction>;
  AAIntraFnReachabilityFunction(const IRPosition &IRP, Attributor &A)
      : Base(IRP, A) {
    DT = A.getInfoCache().getAnalysisResultForFunction<DominatorTreeAnalysis>(
        *IRP.getAssociatedFunction());
  }
 
  bool isAssumedReachable(
      Attributor &A, const Instruction &From, const Instruction &To,
      const AA::InstExclusionSetTy *ExclusionSet) const override {
    auto *NonConstThis = const_cast<AAIntraFnReachabilityFunction *>(this);
    if (&From == &To)
      return true;
 
    RQITy StackRQI(A, From, To, ExclusionSet, false);
    typename RQITy::Reachable Result;
    if (!NonConstThis->checkQueryCache(A, StackRQI, Result))
      return NonConstThis->isReachableImpl(A, StackRQI,
                                           /*IsTemporaryRQI=*/true);
    return Result == RQITy::Reachable::Yes;
  }
 
  ChangeStatus updateImpl(Attributor &A) override {
    // We only depend on liveness. DeadEdges is all we care about, check if any
    // of them changed.
    auto *LivenessAA =
        A.getAAFor<AAIsDead>(*this, getIRPosition(), DepClassTy::OPTIONAL);
    if (LivenessAA &&
        llvm::all_of(DeadEdges,
                     [&](const auto &DeadEdge) {
                       return LivenessAA->isEdgeDead(DeadEdge.first,
                                                     DeadEdge.second);
                     }) &&
        llvm::all_of(DeadBlocks, [&](const BasicBlock *BB) {
          return LivenessAA->isAssumedDead(BB);
        })) {
      return ChangeStatus::UNCHANGED;
    }
    DeadEdges.clear();
    DeadBlocks.clear();
    return Base::updateImpl(A);
  }
 
  bool isReachableImpl(Attributor &A, RQITy &RQI,
                       bool IsTemporaryRQI) override {
    const Instruction *Origin = RQI.From;
    bool UsedExclusionSet = false;
 
    auto WillReachInBlock = [&](const Instruction &From, const Instruction &To,
                                const AA::InstExclusionSetTy *ExclusionSet) {
      const Instruction *IP = &From;
      while (IP && IP != &To) {
        if (ExclusionSet && IP != Origin && ExclusionSet->count(IP)) {
          UsedExclusionSet = true;
          break;
        }
        IP = IP->getNextNode();
      }
      return IP == &To;
    };
 
    const BasicBlock *FromBB = RQI.From->getParent();
    const BasicBlock *ToBB = RQI.To->getParent();
    assert(FromBB->getParent() == ToBB->getParent() &&
           "Not an intra-procedural query!");
 
    // Check intra-block reachability, however, other reaching paths are still
    // possible.
    if (FromBB == ToBB &&
        WillReachInBlock(*RQI.From, *RQI.To, RQI.ExclusionSet))
      return rememberResult(A, RQITy::Reachable::Yes, RQI, UsedExclusionSet,
                            IsTemporaryRQI);
 
    // Check if reaching the ToBB block is sufficient or if even that would not
    // ensure reaching the target. In the latter case we are done.
    if (!WillReachInBlock(ToBB->front(), *RQI.To, RQI.ExclusionSet))
      return rememberResult(A, RQITy::Reachable::No, RQI, UsedExclusionSet,
                            IsTemporaryRQI);
 
    const Function *Fn = FromBB->getParent();
    SmallPtrSet<const BasicBlock *, 16> ExclusionBlocks;
    if (RQI.ExclusionSet)
      for (auto *I : *RQI.ExclusionSet)
        if (I->getFunction() == Fn)
          ExclusionBlocks.insert(I->getParent());
 
    // Check if we make it out of the FromBB block at all.
    if (ExclusionBlocks.count(FromBB) &&
        !WillReachInBlock(*RQI.From, *FromBB->getTerminator(),
                          RQI.ExclusionSet))
      return rememberResult(A, RQITy::Reachable::No, RQI, true, IsTemporaryRQI);
 
    auto *LivenessAA =
        A.getAAFor<AAIsDead>(*this, getIRPosition(), DepClassTy::OPTIONAL);
    if (LivenessAA && LivenessAA->isAssumedDead(ToBB)) {
      DeadBlocks.insert(ToBB);
      return rememberResult(A, RQITy::Reachable::No, RQI, UsedExclusionSet,
                            IsTemporaryRQI);
    }
 
    SmallPtrSet<const BasicBlock *, 16> Visited;
    SmallVector<const BasicBlock *, 16> Worklist;
    Worklist.push_back(FromBB);
 
    DenseSet<std::pair<const BasicBlock *, const BasicBlock *>> LocalDeadEdges;
    while (!Worklist.empty()) {
      const BasicBlock *BB = Worklist.pop_back_val();
      if (!Visited.insert(BB).second)
        continue;
      for (const BasicBlock *SuccBB : successors(BB)) {
        if (LivenessAA && LivenessAA->isEdgeDead(BB, SuccBB)) {
          LocalDeadEdges.insert({BB, SuccBB});
          continue;
        }
        // We checked before if we just need to reach the ToBB block.
        if (SuccBB == ToBB)
          return rememberResult(A, RQITy::Reachable::Yes, RQI, UsedExclusionSet,
                                IsTemporaryRQI);
        if (DT && ExclusionBlocks.empty() && DT->dominates(BB, ToBB))
          return rememberResult(A, RQITy::Reachable::Yes, RQI, UsedExclusionSet,
                                IsTemporaryRQI);
 
        if (ExclusionBlocks.count(SuccBB)) {
          UsedExclusionSet = true;
          continue;
        }
        Worklist.push_back(SuccBB);
      }
    }
 
    DeadEdges.insert(LocalDeadEdges.begin(), LocalDeadEdges.end());
    return rememberResult(A, RQITy::Reachable::No, RQI, UsedExclusionSet,
                          IsTemporaryRQI);
  }
 
  /// See AbstractAttribute::trackStatistics()
  void trackStatistics() const override {}
 
private:
  // Set of assumed dead blocks we used in the last query. If any changes we
  // update the state.
  DenseSet<const BasicBlock *> DeadBlocks;
 
  // Set of assumed dead edges we used in the last query. If any changes we
  // update the state.
  DenseSet<std::pair<const BasicBlock *, const BasicBlock *>> DeadEdges;
 
  /// The dominator tree of the function to short-circuit reasoning.
  const DominatorTree *DT = nullptr;
};
} // namespace
 
/// ------------------------ NoAlias Argument Attribute ------------------------
 
bool AANoAlias::isImpliedByIR(Attributor &A, const IRPosition &IRP,
                              Attribute::AttrKind ImpliedAttributeKind,
                              bool IgnoreSubsumingPositions) {
  assert(ImpliedAttributeKind == Attribute::NoAlias &&
         "Unexpected attribute kind");
  Value *Val = &IRP.getAssociatedValue();
  if (IRP.getPositionKind() != IRP_CALL_SITE_ARGUMENT) {
    if (isa<AllocaInst>(Val))
      return true;
  } else {
    IgnoreSubsumingPositions = true;
  }
 
  if (isa<UndefValue>(Val))
    return true;
 
  if (isa<ConstantPointerNull>(Val) &&
      !NullPointerIsDefined(IRP.getAnchorScope(),
                            Val->getType()->getPointerAddressSpace()))
    return true;
 
  if (A.hasAttr(IRP, {Attribute::ByVal, Attribute::NoAlias},
                IgnoreSubsumingPositions, Attribute::NoAlias))
    return true;
 
  return false;
}
 
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(Attributor *A) 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::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::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.
    bool IsKnownNoSycn;
    if (AA::hasAssumedIRAttr<Attribute::NoSync>(
            A, this, IRPosition::function_scope(getIRPosition()),
            DepClassTy::OPTIONAL, IsKnownNoSycn))
      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) {}
 
  /// 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 && 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 && 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().getAnalysisResultForFunction<AAManager>(
          *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) {
    // 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.
 
    auto IsDereferenceableOrNull = [&](Value *O, const DataLayout &DL) {
      const auto *DerefAA = A.getAAFor<AADereferenceable>(
          *this, IRPosition::value(*O), DepClassTy::OPTIONAL);
      return DerefAA ? DerefAA->getAssumedDereferenceableBytes() : 0;
    };
 
    const IRPosition &VIRP = IRPosition::value(getAssociatedValue());
    const Function *ScopeFn = VIRP.getAnchorScope();
    // 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);
 
            bool IsKnownNoCapture;
            if (AA::hasAssumedIRAttr<Attribute::NoCapture>(
                    A, this, IRPosition::callsite_argument(*CB, ArgNo),
                    DepClassTy::OPTIONAL, IsKnownNoCapture))
              return true;
          }
        }
 
        if (!AA::isPotentiallyReachable(
                A, *UserI, *getCtxI(), *this, /* ExclusionSet */ nullptr,
                [ScopeFn](const Function &Fn) { return &Fn != ScopeFn; }))
          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");
    };
 
    bool IsKnownNoCapture;
    const AANoCapture *NoCaptureAA = nullptr;
    bool IsAssumedNoCapture = AA::hasAssumedIRAttr<Attribute::NoCapture>(
        A, this, VIRP, DepClassTy::NONE, IsKnownNoCapture, false, &NoCaptureAA);
    if (!IsAssumedNoCapture &&
        (!NoCaptureAA || !NoCaptureAA->isAssumedNoCaptureMaybeReturned())) {
      if (!A.checkForAllUses(UsePred, *this, getAssociatedValue())) {
        LLVM_DEBUG(
            dbgs() << "[AANoAliasCSArg] " << getAssociatedValue()
                   << " cannot be noalias as it is potentially captured\n");
        return false;
      }
    }
    if (NoCaptureAA)
      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 && MemBehaviorAA->isAssumedReadNone()) {
      A.recordDependence(*MemBehaviorAA, *this, DepClassTy::OPTIONAL);
      return ChangeStatus::UNCHANGED;
    }
 
    bool IsKnownNoAlias;
    const IRPosition &VIRP = IRPosition::value(getAssociatedValue());
    if (!AA::hasAssumedIRAttr<Attribute::NoAlias>(
            A, this, VIRP, DepClassTy::REQUIRED, IsKnownNoAlias)) {
      LLVM_DEBUG(dbgs() << "[AANoAlias] " << getAssociatedValue()
                        << " is not no-alias at the definition\n");
      return indicatePessimisticFixpoint();
    }
 
    AAResults *AAR = nullptr;
    if (MemBehaviorAA &&
        isKnownNoAliasDueToNoAliasPreservation(A, AAR, *MemBehaviorAA)) {
      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::updateImpl(...).
  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);
      bool IsKnownNoAlias;
      if (!AA::hasAssumedIRAttr<Attribute::NoAlias>(
              A, this, RVPos, DepClassTy::REQUIRED, IsKnownNoAlias))
        return false;
 
      bool IsKnownNoCapture;
      const AANoCapture *NoCaptureAA = nullptr;
      bool IsAssumedNoCapture = AA::hasAssumedIRAttr<Attribute::NoCapture>(
          A, this, RVPos, DepClassTy::REQUIRED, IsKnownNoCapture, false,
          &NoCaptureAA);
      return IsAssumedNoCapture ||
             (NoCaptureAA && 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
    : AACalleeToCallSite<AANoAlias, AANoAliasImpl> {
  AANoAliasCallSiteReturned(const IRPosition &IRP, Attributor &A)
      : AACalleeToCallSite<AANoAlias, AANoAliasImpl>(IRP, A) {}
 
  /// 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 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().
  const std::string getAsStr(Attributor *A) 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;
      std::optional<Constant *> C =
          A.getAssumedConstant(V, *this, UsedAssumedInformation);
      if (!C || *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);
 
    bool IsKnownNoUnwind;
    if (!AA::hasAssumedIRAttr<Attribute::NoUnwind>(
            A, this, CallIRP, DepClassTy::OPTIONAL, IsKnownNoUnwind))
      return false;
 
    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) && !isa_and_nonnull<FenceInst>(I))
        indicatePessimisticFixpoint();
      else
        removeAssumedBits(HAS_NO_EFFECT);
    }
  }
 
  bool isDeadFence(Attributor &A, FenceInst &FI) {
    const auto *ExecDomainAA = A.lookupAAFor<AAExecutionDomain>(
        IRPosition::function(*FI.getFunction()), *this, DepClassTy::NONE);
    if (!ExecDomainAA || !ExecDomainAA->isNoOpFence(FI))
      return false;
    A.recordDependence(*ExecDomainAA, *this, DepClassTy::OPTIONAL);
    return true;
  }
 
  bool isDeadStore(Attributor &A, StoreInst &SI,
                   SmallSetVector<Instruction *, 8> *AssumeOnlyInst = nullptr) {
    // Lang ref now states volatile store is not UB/dead, let's skip them.
    if (SI.isVolatile())
      return false;
 
    // If we are collecting assumes to be deleted we are in the manifest stage.
    // It's problematic to collect the potential copies again now so we use the
    // cached ones.
    bool UsedAssumedInformation = false;
    if (!AssumeOnlyInst) {
      PotentialCopies.clear();
      if (!AA::getPotentialCopiesOfStoredValue(A, SI, PotentialCopies, *this,
                                               UsedAssumedInformation)) {
        LLVM_DEBUG(
            dbgs()
            << "[AAIsDead] Could not determine potential copies of store!\n");
        return false;
      }
    }
    LLVM_DEBUG(dbgs() << "[AAIsDead] Store has " << PotentialCopies.size()
                      << " potential copies.\n");
 
    InformationCache &InfoCache = A.getInfoCache();
    return llvm::all_of(PotentialCopies, [&](Value *V) {
      if (A.isAssumedDead(IRPosition::value(*V), this, nullptr,
                          UsedAssumedInformation))
        return true;
      if (auto *LI = dyn_cast<LoadInst>(V)) {
        if (llvm::all_of(LI->uses(), [&](const Use &U) {
              auto &UserI = cast<Instruction>(*U.getUser());
              if (InfoCache.isOnlyUsedByAssume(UserI)) {
                if (AssumeOnlyInst)
                  AssumeOnlyInst->insert(&UserI);
                return true;
              }
              return A.isAssumedDead(U, this, nullptr, UsedAssumedInformation);
            })) {
          return true;
        }
      }
      LLVM_DEBUG(dbgs() << "[AAIsDead] Potential copy " << *V
                        << " is assumed live!\n");
      return false;
    });
  }
 
  /// See AbstractAttribute::getAsStr().
  const std::string getAsStr(Attributor *A) const override {
    Instruction *I = dyn_cast<Instruction>(&getAssociatedValue());
    if (isa_and_nonnull<StoreInst>(I))
      if (isValidState())
        return "assumed-dead-store";
    if (isa_and_nonnull<FenceInst>(I))
      if (isValidState())
        return "assumed-dead-fence";
    return AAIsDeadValueImpl::getAsStr(A);
  }
 
  /// 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 (auto *FI = dyn_cast_or_null<FenceInst>(I)) {
      if (!isDeadFence(A, *FI))
        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 (auto *SI = dyn_cast<StoreInst>(I)) {
        SmallSetVector<Instruction *, 8> AssumeOnlyInst;
        bool IsDead = isDeadStore(A, *SI, &AssumeOnlyInst);
        (void)IsDead;
        assert(IsDead && "Store was assumed to be dead!");
        A.deleteAfterManifest(*I);
        for (size_t i = 0; i < AssumeOnlyInst.size(); ++i) {
          Instruction *AOI = AssumeOnlyInst[i];
          for (auto *Usr : AOI->users())
            AssumeOnlyInst.insert(cast<Instruction>(Usr));
          A.deleteAfterManifest(*AOI);
        }
        return ChangeStatus::CHANGED;
      }
      if (auto *FI = dyn_cast<FenceInst>(I)) {
        assert(isDeadFence(A, *FI));
        A.deleteAfterManifest(*FI);
        return ChangeStatus::CHANGED;
      }
      if (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)
  }
 
private:
  // The potential copies of a dead store, used for deletion during manifest.
  SmallSetVector<Value *, 4> PotentialCopies;
};
 
struct AAIsDeadArgument : public AAIsDeadFloating {
  AAIsDeadArgument(const IRPosition &IRP, Attributor &A)
      : AAIsDeadFloating(IRP, A) {}
 
  /// 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);
    if (!ArgAA)
      return indicatePessimisticFixpoint();
    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(Attributor *A) 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();
    assert(F && "Did expect an anchor function");
    if (!isAssumedDeadInternalFunction(A)) {
      ToBeExploredFrom.insert(&F->getEntryBlock().front());
      assumeLive(A, F->getEntryBlock());
    }
  }
 
  bool isAssumedDeadInternalFunction(Attributor &A) {
    if (!getAnchorScope()->hasLocalLinkage())
      return false;
    bool UsedAssumedInformation = false;
    return A.checkForAllCallSites([](AbstractCallSite) { return false; }, *this,
                                  true, UsedAssumedInformation);
  }
 
  /// See AbstractAttribute::getAsStr().
  const std::string getAsStr(Attributor *A) 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;
      bool IsKnownNoReturn;
      bool MayReturn = !AA::hasAssumedIRAttr<Attribute::NoReturn>(
          A, this, IRPosition::callsite_function(*CB), DepClassTy::OPTIONAL,
          IsKnownNoReturn);
      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 (auto *F = dyn_cast_if_present<Function>(CB->getCalledOperand()))
          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);
 
  bool IsKnownNoReturn;
  if (AA::hasAssumedIRAttr<Attribute::NoReturn>(
          A, &AA, IPos, DepClassTy::OPTIONAL, IsKnownNoReturn))
    return !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);
 
    bool IsKnownNoUnwind;
    if (AA::hasAssumedIRAttr<Attribute::NoUnwind>(
            A, &AA, IPos, DepClassTy::OPTIONAL, IsKnownNoUnwind)) {
      UsedAssumedInformation |= !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 {
    std::optional<Constant *> C =
        A.getAssumedConstant(*BI.getCondition(), AA, UsedAssumedInformation);
    if (!C || isa_and_nonnull<UndefValue>(*C)) {
      // 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;
  SmallVector<AA::ValueAndContext> Values;
  if (!A.getAssumedSimplifiedValues(IRPosition::value(*SI.getCondition()), &AA,
                                    Values, AA::AnyScope,
                                    UsedAssumedInformation)) {
    // Something went wrong, assume all successors are live.
    for (const BasicBlock *SuccBB : successors(SI.getParent()))
      AliveSuccessors.push_back(&SuccBB->front());
    return false;
  }
 
  if (Values.empty() ||
      (Values.size() == 1 &&
       isa_and_nonnull<UndefValue>(Values.front().getValue()))) {
    // No valid value yet, assume all edges are dead.
    return UsedAssumedInformation;
  }
 
  Type &Ty = *SI.getCondition()->getType();
  SmallPtrSet<ConstantInt *, 8> Constants;
  auto CheckForConstantInt = [&](Value *V) {
    if (auto *CI = dyn_cast_if_present<ConstantInt>(AA::getWithType(*V, Ty))) {
      Constants.insert(CI);
      return true;
    }
    return false;
  };
 
  if (!all_of(Values, [&](AA::ValueAndContext &VAC) {
        return CheckForConstantInt(VAC.getValue());
      })) {
    for (const BasicBlock *SuccBB : successors(SI.getParent()))
      AliveSuccessors.push_back(&SuccBB->front());
    return UsedAssumedInformation;
  }
 
  unsigned MatchedCases = 0;
  for (const auto &CaseIt : SI.cases()) {
    if (Constants.count(CaseIt.getCaseValue())) {
      ++MatchedCases;
      AliveSuccessors.push_back(&CaseIt.getCaseSuccessor()->front());
    }
  }
 
  // If all potential values have been matched, we will not visit the default
  // case.
  if (MatchedCases < Constants.size())
    AliveSuccessors.push_back(&SI.getDefaultDest()->front());
  return UsedAssumedInformation;
}
 
ChangeStatus AAIsDeadFunction::updateImpl(Attributor &A) {
  ChangeStatus Change = ChangeStatus::UNCHANGED;
 
  if (AssumedLiveBlocks.empty()) {
    if (isAssumedDeadInternalFunction(A))
      return ChangeStatus::UNCHANGED;
 
    Function *F = getAnchorScope();
    ToBeExploredFrom.insert(&F->getEntryBlock().front());
    assumeLive(A, F->getEntryBlock());
    Change = ChangeStatus::CHANGED;
  }
 
  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 {
    Value &V = *getAssociatedValue().stripPointerCasts();
    SmallVector<Attribute, 4> Attrs;
    A.getAttrs(getIRPosition(),
               {Attribute::Dereferenceable, Attribute::DereferenceableOrNull},
               Attrs, /* IgnoreSubsumingPositions */ false);
    for (const Attribute &Attr : Attrs)
      takeKnownDerefBytesMaximum(Attr.getValueAsInt());
 
    // Ensure we initialize the non-null AA (if necessary).
    bool IsKnownNonNull;
    AA::hasAssumedIRAttr<Attribute::NonNull>(
        A, this, getIRPosition(), DepClassTy::OPTIONAL, IsKnownNonNull);
 
    bool CanBeNull, CanBeFreed;
    takeKnownDerefBytesMaximum(V.getPointerDereferenceableBytes(
        A.getDataLayout(), CanBeNull, CanBeFreed));
 
    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;
 
    std::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 *