//===- Interpreter.cpp - Interpreter Loop for llubi -----------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// This file implements the evaluation loop for each kind of instruction.
//
//===----------------------------------------------------------------------===//

#include "Context.h"
#include "ExecutorBase.h"
#include "Library.h"
#include "Value.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/VectorUtils.h"
#include "llvm/IR/GetElementPtrTypeIterator.h"
#include "llvm/IR/InlineAsm.h"
#include "llvm/IR/InstVisitor.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Support/Allocator.h"
#include "llvm/TargetParser/Triple.h"

#include <limits>

namespace llvm::ubi {

using namespace PatternMatch;

static AnyValue addNoWrap(const APInt &LHS, const APInt &RHS, bool HasNSW,
                          bool HasNUW) {
  APInt Res = LHS + RHS;
  if (HasNUW && Res.ult(RHS))
    return AnyValue::poison();
  if (HasNSW && LHS.isNonNegative() == RHS.isNonNegative() &&
      LHS.isNonNegative() != Res.isNonNegative())
    return AnyValue::poison();
  return Res;
}

static AnyValue subNoWrap(const APInt &LHS, const APInt &RHS, bool HasNSW,
                          bool HasNUW) {
  APInt Res = LHS - RHS;
  if (HasNUW && Res.ugt(LHS))
    return AnyValue::poison();
  if (HasNSW && LHS.isNonNegative() != RHS.isNonNegative() &&
      LHS.isNonNegative() != Res.isNonNegative())
    return AnyValue::poison();
  return Res;
}

static AnyValue mulNoWrap(const APInt &LHS, const APInt &RHS, bool HasNSW,
                          bool HasNUW) {
  bool Overflow = false;
  APInt Res = LHS.smul_ov(RHS, Overflow);
  if (HasNSW && Overflow)
    return AnyValue::poison();
  if (HasNUW) {
    (void)LHS.umul_ov(RHS, Overflow);
    if (Overflow)
      return AnyValue::poison();
  }
  return Res;
}

/// Visit the scalar values recursively. The callback function may modify the
/// value in-place.
static void forEachScalarValue(AnyValue &V,
                               function_ref<void(AnyValue &)> Visit) {
  if (V.isNone())
    return;

  if (V.isAggregate()) {
    for (auto &SubValue : V.asAggregate())
      forEachScalarValue(SubValue, Visit);
    return;
  }

  Visit(V);
}

static void applyRangeAttr(AnyValue &V, const ConstantRange &CR) {
  forEachScalarValue(V, [&](AnyValue &Scalar) {
    if (Scalar.isInteger() && !CR.contains(Scalar.asInteger()))
      Scalar = AnyValue::poison();
  });
}

static void applyNoFPClassAttr(AnyValue &V, FPClassTest NoFPClass) {
  forEachScalarValue(V, [NoFPClass](AnyValue &Scalar) {
    if (Scalar.isFloat() && (Scalar.asFloat().classify() & NoFPClass))
      Scalar = AnyValue::poison();
  });
}

static void applyNonNullAttr(AnyValue &V, unsigned AS, const DataLayout &DL) {
  if (V.isPointer() && V.asPointer().isNullPtr(AS, DL))
    V = AnyValue::poison();
}

static void applyAlignAttr(AnyValue &V, Align Alignment) {
  forEachScalarValue(V, [Alignment](AnyValue &Scalar) {
    if (Scalar.isPointer() &&
        Scalar.asPointer().address().countr_zero() < Log2(Alignment))
      Scalar = AnyValue::poison();
  });
}

static bool violatesNoUndefAttr(AnyValue &V) {
  bool ContainsPoison = false;
  forEachScalarValue(
      V, [&](AnyValue &Scalar) { ContainsPoison |= Scalar.isPoison(); });
  return ContainsPoison;
}

/// Assumes V is either a poison or a pointer.
static bool violatesDereferenceableBytesAttr(const AnyValue &V, uint64_t Bytes,
                                             bool OrNull, unsigned AS,
                                             const DataLayout &DL) {
  if (V.isPoison())
    return true;

  auto &Ptr = V.asPointer();
  if (Ptr.isNullPtr(AS, DL)) {
    if (OrNull)
      return false;
    return true;
  }
  auto *MO = Ptr.getMemoryObject();
  if (!MO)
    return true;

  // TODO: check read_provenance
  // TODO: check nofree for attributes/metadata.

  const APInt &PtrAddr = Ptr.address();
  return Bytes > MO->getSize() || PtrAddr.ult(MO->getAddress()) ||
         PtrAddr.ugt(MO->getAddress() + MO->getSize() - Bytes);
}

/// Instruction executor using the visitor pattern.
/// Unlike the Context class that manages the global state,
/// InstExecutor only maintains the state for call frames.
class InstExecutor : public InstVisitor<InstExecutor, void>,
                     public ExecutorBase {
  const DataLayout &DL;
  std::list<Frame> CallStack;
  AnyValue None;
  std::list<AnyValue> UnsupportedConstantValues;
  Library Lib;

  const AnyValue &getValue(Value *V) {
    if (auto *C = dyn_cast<Constant>(V)) {
      if (const AnyValue *Val = Ctx.getConstantValue(C))
        return *Val;
      reportError() << "Unsupported constant: " << *C << ".";
      UnsupportedConstantValues.push_back(
          AnyValue::getPoisonValue(Ctx, C->getType()));
      return UnsupportedConstantValues.back();
    }
    return CurrentFrame->ValueMap.at(V);
  }

  void setResult(Instruction &I, AnyValue V) {
    if (!hasProgramExited() && !Handler.onInstructionExecuted(I, V))
      setFailed();
    assert(V.isCompatibleWith(I.getType()) && "Unexpected value storage kind.");
    if (!V.isNone())
      CurrentFrame->ValueMap.insert_or_assign(&I, std::move(V));
  }

  APFloat handleDenormal(APFloat Val, DenormalMode::DenormalModeKind Mode,
                         bool IsInput) {
    if (!Val.isDenormal())
      return Val;
    if (IsInput) {
      // Non-deterministically choose between flushing or preserving the
      // denormal value.
      if (Ctx.getRandomBool())
        return Val;
    }
    if (Mode == DenormalMode::PositiveZero)
      return APFloat::getZero(Val.getSemantics(), false);
    if (Mode == DenormalMode::PreserveSign)
      return APFloat::getZero(Val.getSemantics(), Val.isNegative());
    // Default case for IEEE, Dynamic, and Invalid
    // Currently we treat Dynamic the same as IEEE, since we don't support
    // changing the mode at this point.
    return Val;
  }

  AnyValue handleFMFFlags(AnyValue Val, FastMathFlags FMF, bool IsInput) {
    if (Val.isPoison())
      return AnyValue::poison();

    if (Val.isAggregate()) {
      std::vector<AnyValue> ResVec;
      ResVec.reserve(Val.asAggregate().size());
      for (const auto &A : Val.asAggregate())
        ResVec.push_back(handleFMFFlags(A, FMF, IsInput));
      return AnyValue(ResVec);
    }

    const APFloat &APVal = Val.asFloat();
    if (FMF.noNaNs() && APVal.isNaN())
      return AnyValue::poison();
    if (FMF.noInfs() && APVal.isInfinity())
      return AnyValue::poison();
    if (IsInput && FMF.noSignedZeros() && APVal.isZero())
      return AnyValue(APFloat::getZero(
          APVal.getSemantics(), APVal.isNegative() ^ Ctx.getRandomBool()));
    return Val;
  }

  void addNaNCandidate(SmallVectorImpl<APFloat> &Candidates,
                       APFloat Candidate) {
    if (any_of(Candidates, [&](const APFloat &Existing) {
          return Existing.bitwiseIsEqual(Candidate);
        }))
      return;
    Candidates.push_back(std::move(Candidate));
  }

  APFloat pickNaNCandidate(ArrayRef<APFloat> Candidates) {
    assert(!Candidates.empty() && "Need at least one NaN candidate.");
    return Candidates[Ctx.getRandomUInt64() % Candidates.size()];
  }

  APInt getRandomNaNPayload(const fltSemantics &Sem) {
    const unsigned NumBits = Sem.precision - 1;
    SmallVector<APInt::WordType, 2> RandomWords;
    const unsigned NumWords = APInt::getNumWords(NumBits);
    RandomWords.reserve(NumWords);
    for (unsigned I = 0; I != NumWords; ++I)
      RandomWords.push_back(Ctx.getRandomUInt64());
    return APInt(NumBits, RandomWords);
  }

  bool isPreferredNaN(const APFloat &Val) {
    assert(Val.isNaN() && "Expected NaN.");
    const APFloat Preferred =
        APFloat::getQNaN(Val.getSemantics(), Val.isNegative());
    return Val.bitwiseIsEqual(Preferred);
  }

  bool wasmMayProduceExtraNaNPayload(ArrayRef<const APFloat *> Inputs) {
    for (const APFloat *Input : Inputs) {
      if (!Input->isNaN())
        continue;
      if (Input->isSignaling() || !isPreferredNaN(*Input))
        return true;
    }
    return false;
  }

  APFloat propagateInputNaN(const APFloat &InputNaN, const fltSemantics &DstSem,
                            bool QuietingMode, bool FlipSign) {
    APFloat Res = InputNaN;
    bool LosesInfo;
    Res.convert(DstSem, APFloat::rmNearestTiesToEven, &LosesInfo);
    if (FlipSign)
      Res.changeSign();
    if (QuietingMode && Res.isSignaling())
      Res = Res.makeQuiet();
    return Res;
  }

  APFloat maybeQuietSNaN(APFloat Val) const {
    if (Val.isSignaling() && Ctx.getRandomBool())
      return Val.makeQuiet();
    return Val;
  }

  APFloat maxnumWithSNaNQuieting(const APFloat &LHS, const APFloat &RHS) {
    return maxnum(maybeQuietSNaN(LHS), maybeQuietSNaN(RHS));
  }

  APFloat minnumWithSNaNQuieting(const APFloat &LHS, const APFloat &RHS) {
    return minnum(maybeQuietSNaN(LHS), maybeQuietSNaN(RHS));
  }

  void addPropagatedNaNCandidates(SmallVectorImpl<APFloat> &Candidates,
                                  ArrayRef<const APFloat *> Inputs,
                                  const fltSemantics &DstSem, bool QuietingMode,
                                  bool SignChoice) {
    for (const APFloat *Input : Inputs) {
      if (!Input->isNaN())
        continue;
      addNaNCandidate(Candidates, propagateInputNaN(*Input, DstSem,
                                                    QuietingMode, SignChoice));
    }
  }

  void addTargetSpecificNaNCandidates(SmallVectorImpl<APFloat> &Candidates,
                                      const APFloat &Result,
                                      ArrayRef<const APFloat *> Inputs,
                                      bool SignChoice) {
    const Triple &TT = Ctx.getTargetTriple();
    if (TT.isWasm()) {
      if (!wasmMayProduceExtraNaNPayload(Inputs))
        return;
      APInt Payload = getRandomNaNPayload(Result.getSemantics());
      addNaNCandidate(Candidates, APFloat::getQNaN(Result.getSemantics(),
                                                   SignChoice, &Payload));
      return;
    }

    if (TT.isSPARC32() || TT.isSPARC64()) {
      APInt Payload = APInt::getAllOnes(Result.getSemantics().precision - 1);
      addNaNCandidate(Candidates, APFloat::getQNaN(Result.getSemantics(),
                                                   SignChoice, &Payload));
    }
  }

  APFloat applyNaNPropagation(const APFloat &Result,
                              ArrayRef<const APFloat *> Inputs) {
    if (!Result.isNaN())
      return Result;

    const NaNPropagationBehavior Choice =
        Ctx.getEffectiveNaNPropagationBehavior();
    const bool SignChoice = Ctx.getRandomBool();
    const fltSemantics &ResultSem = Result.getSemantics();
    auto PreferredNaN = [&]() {
      return APFloat::getQNaN(ResultSem, SignChoice);
    };

    SmallVector<APFloat, 4> Candidates;
    switch (Choice) {
    case NaNPropagationBehavior::PreferredNaN:
      return PreferredNaN();
    case NaNPropagationBehavior::QuietingNaN:
      addPropagatedNaNCandidates(Candidates, Inputs, ResultSem,
                                 /*QuietingMode=*/true, SignChoice);
      return Candidates.empty() ? PreferredNaN() : pickNaNCandidate(Candidates);
    case NaNPropagationBehavior::UnchangedNaN:
      addPropagatedNaNCandidates(Candidates, Inputs, ResultSem,
                                 /*QuietingMode=*/false, SignChoice);
      return Candidates.empty() ? PreferredNaN() : pickNaNCandidate(Candidates);
    case NaNPropagationBehavior::TargetSpecificNaN:
      addTargetSpecificNaNCandidates(Candidates, Result, Inputs, SignChoice);
      return Candidates.empty() ? PreferredNaN() : pickNaNCandidate(Candidates);
    case NaNPropagationBehavior::NonDeterministic:
      addNaNCandidate(Candidates, PreferredNaN());
      addPropagatedNaNCandidates(Candidates, Inputs, ResultSem,
                                 /*QuietingMode=*/true, SignChoice);
      addPropagatedNaNCandidates(Candidates, Inputs, ResultSem,
                                 /*QuietingMode=*/false, SignChoice);
      addTargetSpecificNaNCandidates(Candidates, Result, Inputs, SignChoice);
      return pickNaNCandidate(Candidates);
    }
    llvm_unreachable("Unhandled NaN propagation behavior.");
  }

  AnyValue computeUnOp(Type *Ty, const AnyValue &Operand,
                       function_ref<AnyValue(const AnyValue &)> ScalarFn) {
    if (Ty->isVectorTy()) {
      auto &OperandVec = Operand.asAggregate();
      std::vector<AnyValue> ResVec;
      ResVec.reserve(OperandVec.size());
      for (const auto &Scalar : OperandVec)
        ResVec.push_back(ScalarFn(Scalar));
      return std::move(ResVec);
    }
    return ScalarFn(Operand);
  }

  void visitUnOp(Instruction &I,
                 function_ref<AnyValue(const AnyValue &)> ScalarFn) {
    setResult(I, computeUnOp(I.getType(), getValue(I.getOperand(0)), ScalarFn));
  }

  void visitIntUnOp(Instruction &I,
                    function_ref<AnyValue(const APInt &)> ScalarFn) {
    visitUnOp(I, [&](const AnyValue &Operand) -> AnyValue {
      if (Operand.isPoison())
        return AnyValue::poison();
      return ScalarFn(Operand.asInteger());
    });
  }

  void visitBitwiseFPUnOp(Instruction &I,
                          function_ref<APFloat(const APFloat &)> ScalarFn) {
    setResult(I, visitBitwiseFPUnOpWithResult(
                     I.getType(), cast<FPMathOperator>(I).getFastMathFlags(),
                     getValue(I.getOperand(0)), ScalarFn));
  }

  AnyValue
  visitIntUnOpWithResult(Type *RetTy, const AnyValue &Operand,
                         function_ref<AnyValue(const APInt &)> ScalarFn) {
    return computeUnOp(RetTy, Operand,
                       [&](const AnyValue &OperandInner) -> AnyValue {
                         if (OperandInner.isPoison())
                           return AnyValue::poison();
                         return ScalarFn(OperandInner.asInteger());
                       });
  }

  AnyValue visitBitwiseFPUnOpWithResult(
      Type *RetTy, const FastMathFlags &FMF, const AnyValue &Operand,
      function_ref<APFloat(const APFloat &)> ScalarFn) {
    return computeUnOp(
        RetTy, Operand, [&](const AnyValue &OperandInner) -> AnyValue {
          if (OperandInner.isPoison())
            return AnyValue::poison();

          // We don't flush denormals here since bitwise floating-point
          // operations only manipulate on certain bits of the operand.

          AnyValue ValidatedOperand =
              handleFMFFlags(OperandInner, FMF, /*IsInput=*/true);
          if (ValidatedOperand.isPoison())
            return ValidatedOperand;

          APFloat Result = ScalarFn(ValidatedOperand.asFloat());

          return handleFMFFlags(Result, FMF, /*IsInput=*/false);
        });
  }

  AnyValue computeBinOp(
      Type *Ty, const AnyValue &LHS, const AnyValue &RHS,
      function_ref<AnyValue(const AnyValue &, const AnyValue &)> ScalarFn) {
    if (Ty->isVectorTy()) {
      auto &LHSVec = LHS.asAggregate();
      auto &RHSVec = RHS.asAggregate();
      std::vector<AnyValue> ResVec;
      ResVec.reserve(LHSVec.size());
      for (const auto &[ScalarLHS, ScalarRHS] : zip(LHSVec, RHSVec))
        ResVec.push_back(ScalarFn(ScalarLHS, ScalarRHS));
      return std::move(ResVec);
    }
    return ScalarFn(LHS, RHS);
  }

  void visitBinOp(
      Instruction &I,
      function_ref<AnyValue(const AnyValue &, const AnyValue &)> ScalarFn) {
    setResult(I, computeBinOp(I.getType(), getValue(I.getOperand(0)),
                              getValue(I.getOperand(1)), ScalarFn));
  }

  void
  visitIntBinOp(Instruction &I,
                function_ref<AnyValue(const APInt &, const APInt &)> ScalarFn) {
    visitBinOp(I, [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
      if (LHS.isPoison() || RHS.isPoison())
        return AnyValue::poison();
      return ScalarFn(LHS.asInteger(), RHS.asInteger());
    });
  }

  void visitFPBinOp(
      Instruction &I,
      function_ref<APFloat(const APFloat &, const APFloat &)> ScalarFn) {
    setResult(I, visitFPBinOpWithResult(
                     I.getType(), cast<FPMathOperator>(I).getFastMathFlags(),
                     getValue(I.getOperand(0)), getValue(I.getOperand(1)),
                     ScalarFn));
  }

  AnyValue visitIntBinOpWithResult(
      Type *RetTy, const AnyValue &LHS, const AnyValue &RHS,
      function_ref<AnyValue(const APInt &, const APInt &)> ScalarFn) {
    return computeBinOp(
        RetTy, LHS, RHS,
        [&](const AnyValue &LHSInner, const AnyValue &RHSInner) -> AnyValue {
          if (LHSInner.isPoison() || RHSInner.isPoison())
            return AnyValue::poison();
          return ScalarFn(LHSInner.asInteger(), RHSInner.asInteger());
        });
  }

  AnyValue visitOverflowIntBinOpWithResult(
      Type *RetTy, const AnyValue &LHS, const AnyValue &RHS,
      function_ref<std::pair<APInt, bool>(const APInt &, const APInt &)>
          ScalarFn) {
    if (!LHS.isAggregate()) {
      if (LHS.isPoison() || RHS.isPoison())
        return std::vector<AnyValue>{AnyValue::poison(), AnyValue::poison()};
      auto [Res, Overflow] = ScalarFn(LHS.asInteger(), RHS.asInteger());
      return std::vector<AnyValue>{AnyValue(Res), AnyValue::boolean(Overflow)};
    }

    auto &LHSVec = LHS.asAggregate();
    auto &RHSVec = RHS.asAggregate();
    std::vector<AnyValue> ResVec;
    std::vector<AnyValue> OverflowVec;
    ResVec.reserve(LHSVec.size());
    OverflowVec.reserve(LHSVec.size());
    for (const auto &[ScalarLHS, ScalarRHS] : zip(LHSVec, RHSVec)) {
      if (ScalarLHS.isPoison() || ScalarRHS.isPoison()) {
        ResVec.push_back(AnyValue::poison());
        OverflowVec.push_back(AnyValue::poison());
        continue;
      }
      auto [Res, Overflow] =
          ScalarFn(ScalarLHS.asInteger(), ScalarRHS.asInteger());
      ResVec.push_back(AnyValue(Res));
      OverflowVec.push_back(AnyValue::boolean(Overflow));
    }
    return std::vector<AnyValue>{AnyValue(std::move(ResVec)),
                                 AnyValue(std::move(OverflowVec))};
  }

  AnyValue visitFPBinOpWithResult(
      Type *RetTy, const FastMathFlags &FMF, const AnyValue &LHS,
      const AnyValue &RHS,
      function_ref<APFloat(const APFloat &, const APFloat &)> ScalarFn) {
    DenormalMode DenormMode = getCurrentDenormalMode(RetTy);

    if (!Ctx.isDefaultFPEnv())
      reportImmediateUB() << "Non-constrained floating-point operation assumes "
                             "default floating-point environment";

    return computeBinOp(
        RetTy, LHS, RHS,
        [&](const AnyValue &LHSInner, const AnyValue &RHSInner) -> AnyValue {
          if (LHSInner.isPoison() || RHSInner.isPoison())
            return AnyValue::poison();

          AnyValue ValidatedLHS =
              handleFMFFlags(LHSInner, FMF, /*IsInput=*/true);
          AnyValue ValidatedRHS =
              handleFMFFlags(RHSInner, FMF, /*IsInput=*/true);
          if (ValidatedLHS.isPoison())
            return ValidatedLHS;
          if (ValidatedRHS.isPoison())
            return ValidatedRHS;

          // Flush input denormals
          APFloat FLHS = handleDenormal(ValidatedLHS.asFloat(),
                                        DenormMode.Input, /*IsInput=*/true);
          APFloat FRHS = handleDenormal(ValidatedRHS.asFloat(),
                                        DenormMode.Input, /*IsInput=*/true);

          APFloat RawResult = ScalarFn(FLHS, FRHS);

          // Flush output denormals and handle fast-math flags.
          AnyValue FResult = handleFMFFlags(
              handleDenormal(RawResult, DenormMode.Output, /*IsInput=*/false),
              FMF,
              /*IsInput=*/false);

          if (FResult.isPoison())
            return FResult;

          APFloat Result = FResult.asFloat();
          return applyNaNPropagation(Result, {&FLHS, &FRHS});
        });
  }

  AnyValue
  computeTriOp(Type *Ty, const AnyValue &Op1, const AnyValue &Op2,
               const AnyValue &Op3,
               function_ref<AnyValue(const AnyValue &, const AnyValue &,
                                     const AnyValue &)>
                   ScalarFn) {
    if (Ty->isVectorTy()) {
      auto &Op1Vec = Op1.asAggregate();
      auto &Op2Vec = Op2.asAggregate();
      auto &Op3Vec = Op3.asAggregate();
      std::vector<AnyValue> ResVec;
      ResVec.reserve(Op1Vec.size());
      for (const auto &[ScalarOp1, ScalarOp2, ScalarOp3] :
           zip(Op1Vec, Op2Vec, Op3Vec))
        ResVec.push_back(ScalarFn(ScalarOp1, ScalarOp2, ScalarOp3));
      return std::move(ResVec);
    }
    return ScalarFn(Op1, Op2, Op3);
  }

  void visitTriOp(Instruction &I,
                  function_ref<AnyValue(const AnyValue &, const AnyValue &,
                                        const AnyValue &)>
                      ScalarFn) {
    setResult(I, computeTriOp(I.getType(), getValue(I.getOperand(0)),
                              getValue(I.getOperand(1)),
                              getValue(I.getOperand(2)), ScalarFn));
  }

  void visitIntTriOp(
      Instruction &I,
      function_ref<AnyValue(const APInt &, const APInt &, const APInt &)>
          ScalarFn) {
    visitTriOp(I,
               [&](const AnyValue &Op1, const AnyValue &Op2,
                   const AnyValue &Op3) -> AnyValue {
                 if (Op1.isPoison() || Op2.isPoison() || Op3.isPoison())
                   return AnyValue::poison();
                 return ScalarFn(Op1.asInteger(), Op2.asInteger(),
                                 Op3.asInteger());
               });
  }

  AnyValue visitIntTriOpWithResult(
      Type *RetTy, const AnyValue &Op1, const AnyValue &Op2,
      const AnyValue &Op3,
      function_ref<AnyValue(const APInt &, const APInt &, const APInt &)>
          ScalarFn) {
    return computeTriOp(
        RetTy, Op1, Op2, Op3,
        [&](const AnyValue &Op1Inner, const AnyValue &Op2Inner,
            const AnyValue &Op3Inner) -> AnyValue {
          if (Op1Inner.isPoison() || Op2Inner.isPoison() || Op3Inner.isPoison())
            return AnyValue::poison();
          return ScalarFn(Op1Inner.asInteger(), Op2Inner.asInteger(),
                          Op3Inner.asInteger());
        });
  }

  AnyValue visitFPTriOpWithResult(
      Type *RetTy, const FastMathFlags &FMF, const AnyValue &Op1,
      const AnyValue &Op2, const AnyValue &Op3,
      function_ref<APFloat(const APFloat &, const APFloat &, const APFloat &)>
          ScalarFn) {
    DenormalMode DenormMode = getCurrentDenormalMode(RetTy);

    if (!Ctx.isDefaultFPEnv())
      reportImmediateUB() << "Non-constrained floating-point operation assumes "
                             "default floating-point environment";

    return computeTriOp(
        RetTy, Op1, Op2, Op3,
        [&](const AnyValue &Op1Inner, const AnyValue &Op2Inner,
            const AnyValue &Op3Inner) -> AnyValue {
          if (Op1Inner.isPoison() || Op2Inner.isPoison() || Op3Inner.isPoison())
            return AnyValue::poison();

          AnyValue ValidatedOp1 =
              handleFMFFlags(Op1Inner, FMF, /*IsInput=*/true);
          AnyValue ValidatedOp2 =
              handleFMFFlags(Op2Inner, FMF, /*IsInput=*/true);
          AnyValue ValidatedOp3 =
              handleFMFFlags(Op3Inner, FMF, /*IsInput=*/true);
          if (ValidatedOp1.isPoison())
            return ValidatedOp1;
          if (ValidatedOp2.isPoison())
            return ValidatedOp2;
          if (ValidatedOp3.isPoison())
            return ValidatedOp3;

          // Flush input denormals
          APFloat FOp1 = handleDenormal(ValidatedOp1.asFloat(),
                                        DenormMode.Input, /*IsInput=*/true);
          APFloat FOp2 = handleDenormal(ValidatedOp2.asFloat(),
                                        DenormMode.Input, /*IsInput=*/true);
          APFloat FOp3 = handleDenormal(ValidatedOp3.asFloat(),
                                        DenormMode.Input, /*IsInput=*/true);

          APFloat RawResult = ScalarFn(FOp1, FOp2, FOp3);

          // Flush output denormals and handle fast-math flags.
          AnyValue FResult = handleFMFFlags(
              handleDenormal(RawResult, DenormMode.Output, /*IsInput=*/false),
              FMF,
              /*IsInput=*/false);

          if (FResult.isPoison())
            return FResult;

          APFloat Result = FResult.asFloat();
          return applyNaNPropagation(Result, {&FOp1, &FOp2, &FOp3});
        });
  }

  void jumpTo(Instruction &Terminator, BasicBlock *DestBB) {
    if (!Handler.onBBJump(Terminator, *DestBB)) {
      setFailed();
      return;
    }
    BasicBlock *From = CurrentFrame->BB;
    CurrentFrame->BB = DestBB;
    CurrentFrame->PC = DestBB->begin();
    // Update PHI nodes in batch to avoid the interference between PHI nodes.
    // We need to store the incoming values into a temporary buffer.
    // Otherwise, the incoming value may be overwritten before it is
    // used by other PHI nodes.
    SmallVector<std::pair<PHINode *, AnyValue>> IncomingValues;
    PHINode *PHI = nullptr;
    while ((PHI = dyn_cast<PHINode>(CurrentFrame->PC))) {
      AnyValue IncomingVal = getValue(PHI->getIncomingValueForBlock(From));

      // Fast-math flags validation
      if (isa<FPMathOperator>(PHI)) {
        FastMathFlags FMF = PHI->getFastMathFlags();
        if (FMF.any())
          IncomingVal =
              handleFMFFlags(std::move(IncomingVal), FMF, /*IsInput=*/true);
      }

      IncomingValues.emplace_back(PHI, IncomingVal);
      ++CurrentFrame->PC;
    }
    for (auto &[K, V] : IncomingValues)
      setResult(*K, std::move(V));
  }

  /// Helper function to determine whether an inline asm is a no-op, which is
  /// used to implement black_box style optimization blockers.
  bool isNoopInlineAsm(Value *V, Type *RetTy) {
    if (auto *Asm = dyn_cast<InlineAsm>(V))
      return Asm->getAsmString().empty() && RetTy->isVoidTy();
    return false;
  }

  AnyValue computePtrAdd(const Pointer &Ptr, const APInt &Offset,
                         GEPNoWrapFlags Flags, AnyValue &AccumulatedOffset) {
    if (Offset.isZero())
      return Ptr;
    APInt IndexBits = Ptr.address().trunc(Offset.getBitWidth());
    auto NewIndex = addNoWrap(IndexBits, Offset, /*HasNSW=*/false,
                              Flags.hasNoUnsignedWrap());
    if (NewIndex.isPoison())
      return AnyValue::poison();
    if (Flags.hasNoUnsignedSignedWrap()) {
      // The successive addition of the current address, truncated to the
      // pointer index type and interpreted as an unsigned number, and each
      // offset, interpreted as a signed number, does not wrap the pointer index
      // type.
      if (Offset.isNonNegative() ? NewIndex.asInteger().ult(IndexBits)
                                 : NewIndex.asInteger().ugt(IndexBits))
        return AnyValue::poison();
    }
    APInt NewAddr = Ptr.address();
    NewAddr.insertBits(NewIndex.asInteger(), 0);

    auto *MO = Ptr.getMemoryObject();
    if (Flags.isInBounds() && (!MO || !MO->inBounds(NewAddr)))
      return AnyValue::poison();

    if (!AccumulatedOffset.isPoison()) {
      AccumulatedOffset =
          addNoWrap(AccumulatedOffset.asInteger(), Offset,
                    Flags.hasNoUnsignedSignedWrap(), Flags.hasNoUnsignedWrap());
      if (AccumulatedOffset.isPoison())
        return AnyValue::poison();
    }

    // Should not expose provenance here even if the new address doesn't point
    // to the original object.
    return Ptr.getWithNewAddr(NewAddr);
  }

  AnyValue computePtrAdd(const AnyValue &Ptr, const APInt &Offset,
                         GEPNoWrapFlags Flags, AnyValue &AccumulatedOffset) {
    if (Ptr.isPoison())
      return AnyValue::poison();
    return computePtrAdd(Ptr.asPointer(), Offset, Flags, AccumulatedOffset);
  }

  AnyValue computeScaledPtrAdd(const AnyValue &Ptr, const AnyValue &Index,
                               const APInt &Scale, GEPNoWrapFlags Flags,
                               AnyValue &AccumulatedOffset) {
    if (Ptr.isPoison() || Index.isPoison())
      return AnyValue::poison();
    assert(Ptr.isPointer() && Index.isInteger() && "Unexpected type.");
    if (Scale.isOne())
      return computePtrAdd(Ptr, Index.asInteger(), Flags, AccumulatedOffset);
    auto ScaledOffset =
        mulNoWrap(Index.asInteger(), Scale, Flags.hasNoUnsignedSignedWrap(),
                  Flags.hasNoUnsignedWrap());
    if (ScaledOffset.isPoison())
      return AnyValue::poison();
    return computePtrAdd(Ptr, ScaledOffset.asInteger(), Flags,
                         AccumulatedOffset);
  }

  AnyValue canonicalizeIndex(const AnyValue &Idx, unsigned IndexBitWidth,
                             GEPNoWrapFlags Flags) {
    if (Idx.isPoison())
      return AnyValue::poison();
    auto &IdxInt = Idx.asInteger();
    if (IdxInt.getBitWidth() == IndexBitWidth)
      return Idx;
    if (IdxInt.getBitWidth() > IndexBitWidth) {
      if (Flags.hasNoUnsignedSignedWrap() &&
          !IdxInt.isSignedIntN(IndexBitWidth))
        return AnyValue::poison();

      if (Flags.hasNoUnsignedWrap() && !IdxInt.isIntN(IndexBitWidth))
        return AnyValue::poison();

      return IdxInt.trunc(IndexBitWidth);
    }
    return IdxInt.sext(IndexBitWidth);
  }

  DenormalMode getCurrentDenormalMode(Type *Ty) {
    return CurrentFrame->Func.getDenormalMode(
        Ty->getScalarType()->getFltSemantics());
  }

  // Helper function to convert BooleanKind to bool. Report an immediate UB if
  // a poison is found.
  bool getBooleanNonPoison(BooleanKind Boolean) {
    if (Boolean == BooleanKind::Poison)
      reportImmediateUB() << "Unexpected poison boolean value";
    return Boolean == BooleanKind::True;
  }

  APInt getIntNonPoison(const AnyValue &V) {
    if (V.isPoison()) {
      reportImmediateUB() << "Unexpected poison integer value.";
      return APInt::getZero(64);
    }
    return V.asInteger();
  }

public:
  InstExecutor(Context &C, EventHandler &H, Function &F,
               ArrayRef<AnyValue> Args, AnyValue &RetVal)
      : ExecutorBase(C, H), DL(Ctx.getDataLayout()),
        Lib(Ctx, Handler, DL, static_cast<ExecutorBase &>(*this)) {
    CallStack.emplace_back(F, /*CallSite=*/nullptr, /*LastFrame=*/nullptr, Args,
                           RetVal, Ctx.getTLIImpl());
  }

  void visitReturnInst(ReturnInst &RI) {
    if (auto *RV = RI.getReturnValue())
      CurrentFrame->RetVal = getValue(RV);
    CurrentFrame->State = FrameState::Exit;
    if (!Handler.onInstructionExecuted(RI, None))
      setFailed();
  }

  void visitUncondBrInst(UncondBrInst &BI) { jumpTo(BI, BI.getSuccessor()); }

  void visitCondBrInst(CondBrInst &BI) {
    switch (getValue(BI.getCondition()).asBoolean()) {
    case BooleanKind::True:
      jumpTo(BI, BI.getSuccessor(0));
      return;
    case BooleanKind::False:
      jumpTo(BI, BI.getSuccessor(1));
      return;
    case BooleanKind::Poison:
      reportImmediateUB() << "Branch on poison condition.";
      return;
    }
  }

  void visitSwitchInst(SwitchInst &SI) {
    auto &Cond = getValue(SI.getCondition());
    if (Cond.isPoison()) {
      reportImmediateUB() << "Switch on poison condition.";
      return;
    }
    for (auto &Case : SI.cases()) {
      if (Case.getCaseValue()->getValue() == Cond.asInteger()) {
        jumpTo(SI, Case.getCaseSuccessor());
        return;
      }
    }
    jumpTo(SI, SI.getDefaultDest());
  }

  void visitUnreachableInst(UnreachableInst &) {
    reportImmediateUB() << "Unreachable code.";
  }

  void visitCallBrInst(CallBrInst &CI) {
    if (isNoopInlineAsm(CI.getCalledOperand(), CI.getType())) {
      jumpTo(CI, CI.getDefaultDest());
      return;
    }

    Handler.onUnrecognizedInstruction(CI);
    setFailed();
  }

  void visitIndirectBrInst(IndirectBrInst &IBI) {
    auto &Target = getValue(IBI.getAddress());
    if (Target.isPoison()) {
      reportImmediateUB() << "Indirect branch on poison.";
      return;
    }
    if (BasicBlock *DestBB = Ctx.getTargetBlock(Target.asPointer())) {
      if (any_of(IBI.successors(),
                 [DestBB](BasicBlock *Succ) { return Succ == DestBB; }))
        jumpTo(IBI, DestBB);
      else
        reportImmediateUB() << "Indirect branch on unlisted target BB.";

      return;
    }
    reportImmediateUB() << "Indirect branch on invalid target BB.";
  }

  void returnFromCallee() {
    auto &CB = cast<CallBase>(*CurrentFrame->PC);
    CurrentFrame->CalleeArgs.clear();
    AnyValue &RetVal = CurrentFrame->CalleeRetVal;
    if (Type *RetTy = CB.getType(); !RetTy->isVoidTy()) {
      // Handle attributes on the return value (Attributes from resolved callee
      // should be applied if available).
      AttributeSet AttrsAtCallSite = CB.getRetAttributes();
      AttributeSet AttrsAtCallee =
          CurrentFrame->ResolvedCallee->getAttributes().getRetAttrs();
      handleAttributes(RetTy, RetVal, AttrsAtCallSite, AttrsAtCallee);
      handleMetadata(RetTy, RetVal, CB);
    }
    setResult(CB, std::move(RetVal));

    if (auto *II = dyn_cast<InvokeInst>(&CB))
      jumpTo(*II, II->getNormalDest());
    else if (CurrentFrame->State == FrameState::Pending)
      ++CurrentFrame->PC;
  }

  AnyValue callIntrinsic(CallBase &CB, ArrayRef<AnyValue> Args) {
    Intrinsic::ID IID = CB.getIntrinsicID();
    Type *RetTy = CB.getType();
    const FastMathFlags FMF = CB.getFastMathFlagsOrNone();

    switch (IID) {
    case Intrinsic::assume:
      switch (Args[0].asBoolean()) {
      case BooleanKind::True:
        for (unsigned Idx = 0; Idx < CB.getNumOperandBundles(); Idx++) {
          OperandBundleUse OBU = CB.getOperandBundleAt(Idx);
          auto GetBundleArg = [&](uint32_t Offset) -> Value * {
            return OBU.Inputs[Offset];
          };
          if (OBU.Inputs.empty())
            continue;
          Value *WasOnVal = GetBundleArg(0);
          // Bail out on unrecognized operand bundles.
          if (!WasOnVal->getType()->isPointerTy())
            continue;
          unsigned AS = WasOnVal->getType()->getPointerAddressSpace();
          const AnyValue &WasOn = getValue(WasOnVal);
          if (WasOn.isPoison()) {
            reportImmediateUB() << "Assume on poison pointer.";
            break;
          }
          const Pointer &WasOnPtr = WasOn.asPointer();
          Attribute::AttrKind Kind =
              Attribute::getAttrKindFromName(OBU.getTagName());
          switch (Kind) {
          case Attribute::Alignment: {
            // Alignment assumptions should have 2 or 3 arguments.
            // If there are two integer arguments, use the largest power of 2
            // that divides them as the alignment.
            APInt Alignment = getIntNonPoison(getValue(GetBundleArg(1)));
            if (OBU.Inputs.size() == 3) {
              APInt Offset = getIntNonPoison(getValue(GetBundleArg(2)));
              if (!Alignment.isZero() || !Offset.isZero())
                Alignment = APInt::getOneBitSet(
                    std::max(Alignment.getBitWidth(), Offset.getBitWidth()),
                    std::min(Alignment.countr_zero(), Offset.countr_zero()));
            }
            if (!Alignment.isPowerOf2()) {
              if (!WasOnPtr.address().isZero())
                reportImmediateUB() << "Assume on nonzero pointer " << WasOn
                                    << " with a "
                                       "non-power-of-two alignment "
                                    << Alignment << '.';
              break;
            }
            if (WasOnPtr.address().countr_zero() < Alignment.logBase2())
              reportImmediateUB()
                  << "The pointer " << WasOn << " violates align(" << Alignment
                  << ") assumption.";
            break;
          }
          case Attribute::NonNull:
            if (WasOnPtr.isNullPtr(AS, DL))
              reportImmediateUB()
                  << "The pointer " << WasOn << " violates nonnull assumption.";
            break;
          case Attribute::Dereferenceable:
          case Attribute::DereferenceableOrNull: {
            APInt DereferenceableBytes =
                getIntNonPoison(getValue(GetBundleArg(1)));
            // Only n > 0 implies that the pointer is dereferenceable.
            if (DereferenceableBytes.isZero())
              break;
            if (violatesDereferenceableBytesAttr(
                    WasOn, DereferenceableBytes.getLimitedValue(),
                    Kind == Attribute::DereferenceableOrNull, AS, DL))
              reportImmediateUB() << "The pointer " << WasOn << " violates "
                                  << (Kind == Attribute::DereferenceableOrNull
                                          ? "dereferenceable_or_null("
                                          : "dereferenceable(")
                                  << DereferenceableBytes << ") assumption.";
            break;
          }
          default:
            // TODO: handle other operand bundles like separate_storage.
            break;
          }
        }
        break;
      case BooleanKind::False:
      case BooleanKind::Poison:
        reportImmediateUB() << "Assume on false or poison condition.";
        break;
      }
      return AnyValue();
    case Intrinsic::lifetime_start:
    case Intrinsic::lifetime_end: {
      auto Ptr = Args[0];
      if (Ptr.isPoison())
        return AnyValue();
      auto *MO = Ptr.asPointer().getMemoryObject();
      assert(MO && "Memory object accessed by lifetime intrinsic should be "
                   "always valid.");
      if (IID == Intrinsic::lifetime_start) {
        MO->setState(MemoryObjectState::Alive);
        fill(MO->getBytes(), Byte::undef());
      } else {
        MO->setState(MemoryObjectState::Dead);
      }
      return AnyValue();
    }
    case Intrinsic::ssa_copy:
    case Intrinsic::expect:
    case Intrinsic::expect_with_probability:
      return Args[0];
    case Intrinsic::donothing:
      return AnyValue();
    case Intrinsic::vscale: {
      const unsigned BitWidth = RetTy->getScalarSizeInBits();
      const APInt VScale(64, Ctx.getVScale());
      if (!VScale.isIntN(BitWidth))
        return AnyValue::poison();
      return VScale.zextOrTrunc(BitWidth);
    }
    case Intrinsic::abs: {
      const bool IsIntMinPoison = getBooleanNonPoison(Args[1].asBoolean());
      return visitIntUnOpWithResult(
          RetTy, Args[0], [&](const APInt &Operand) -> AnyValue {
            if (IsIntMinPoison && Operand.isMinSignedValue())
              return AnyValue::poison();
            return Operand.abs();
          });
    }
    case Intrinsic::smax: {
      return visitIntBinOpWithResult(
          RetTy, Args[0], Args[1],
          [](const APInt &LHS, const APInt &RHS) -> AnyValue {
            return APIntOps::smax(LHS, RHS);
          });
    }
    case Intrinsic::smin: {
      return visitIntBinOpWithResult(
          RetTy, Args[0], Args[1],
          [](const APInt &LHS, const APInt &RHS) -> AnyValue {
            return APIntOps::smin(LHS, RHS);
          });
    }
    case Intrinsic::umax: {
      return visitIntBinOpWithResult(
          RetTy, Args[0], Args[1],
          [](const APInt &LHS, const APInt &RHS) -> AnyValue {
            return APIntOps::umax(LHS, RHS);
          });
    }
    case Intrinsic::umin: {
      return visitIntBinOpWithResult(
          RetTy, Args[0], Args[1],
          [](const APInt &LHS, const APInt &RHS) -> AnyValue {
            return APIntOps::umin(LHS, RHS);
          });
    }
    case Intrinsic::scmp:
    case Intrinsic::ucmp: {
      const unsigned BitWidth = RetTy->getScalarSizeInBits();
      return visitIntBinOpWithResult(
          RetTy, Args[0], Args[1],
          [&](const APInt &LHS, const APInt &RHS) -> AnyValue {
            if (LHS == RHS)
              return APInt::getZero(BitWidth);
            if (IID == Intrinsic::scmp)
              return LHS.slt(RHS) ? APInt::getAllOnes(BitWidth)
                                  : APInt(BitWidth, 1);
            return LHS.ult(RHS) ? APInt::getAllOnes(BitWidth)
                                : APInt(BitWidth, 1);
          });
    }
    case Intrinsic::bitreverse: {
      return visitIntUnOpWithResult(RetTy, Args[0],
                                    [](const APInt &Operand) -> AnyValue {
                                      return Operand.reverseBits();
                                    });
    }
    case Intrinsic::bswap: {
      return visitIntUnOpWithResult(
          RetTy, Args[0],
          [](const APInt &Operand) -> AnyValue { return Operand.byteSwap(); });
    }
    case Intrinsic::ctpop: {
      return visitIntUnOpWithResult(
          RetTy, Args[0], [](const APInt &Operand) -> AnyValue {
            return APInt(Operand.getBitWidth(), Operand.popcount());
          });
    }
    case Intrinsic::ctlz:
    case Intrinsic::cttz: {
      const bool IsZeroPoison = getBooleanNonPoison(Args[1].asBoolean());
      return visitIntUnOpWithResult(
          RetTy, Args[0], [&](const APInt &Operand) -> AnyValue {
            if (IsZeroPoison && Operand.isZero())
              return AnyValue::poison();
            if (IID == Intrinsic::ctlz)
              return APInt(Operand.getBitWidth(), Operand.countl_zero());
            return APInt(Operand.getBitWidth(), Operand.countr_zero());
          });
    }
    case Intrinsic::fshl:
    case Intrinsic::fshr: {
      return visitIntTriOpWithResult(
          RetTy, Args[0], Args[1], Args[2],
          [IID](const APInt &Op1, const APInt &Op2,
                const APInt &Op3) -> AnyValue {
            const unsigned BitWidth = Op1.getBitWidth();
            const uint64_t ShiftAmount = Op3.urem(BitWidth);
            const bool IsFShr = IID == Intrinsic::fshr;
            if (ShiftAmount == 0)
              return IsFShr ? Op2 : Op1;
            const uint64_t LShrAmount =
                IsFShr ? ShiftAmount : BitWidth - ShiftAmount;
            const uint64_t ShlAmount =
                !IsFShr ? ShiftAmount : BitWidth - ShiftAmount;
            return Op1.shl(ShlAmount) | Op2.lshr(LShrAmount);
          });
    }
    case Intrinsic::clmul: {
      return visitIntBinOpWithResult(
          RetTy, Args[0], Args[1],
          [](const APInt &LHS, const APInt &RHS) -> AnyValue {
            return APIntOps::clmul(LHS, RHS);
          });
    }
    case Intrinsic::sadd_with_overflow:
    case Intrinsic::uadd_with_overflow:
    case Intrinsic::ssub_with_overflow:
    case Intrinsic::usub_with_overflow:
    case Intrinsic::smul_with_overflow:
    case Intrinsic::umul_with_overflow: {
      return visitOverflowIntBinOpWithResult(
          RetTy, Args[0], Args[1],
          [IID](const APInt &LHS, const APInt &RHS) -> std::pair<APInt, bool> {
            APInt Res;
            bool Overflow = false;
            switch (IID) {
            case Intrinsic::sadd_with_overflow:
              Res = LHS.sadd_ov(RHS, Overflow);
              break;
            case Intrinsic::uadd_with_overflow:
              Res = LHS.uadd_ov(RHS, Overflow);
              break;
            case Intrinsic::ssub_with_overflow:
              Res = LHS.ssub_ov(RHS, Overflow);
              break;
            case Intrinsic::usub_with_overflow:
              Res = LHS.usub_ov(RHS, Overflow);
              break;
            case Intrinsic::smul_with_overflow:
              Res = LHS.smul_ov(RHS, Overflow);
              break;
            case Intrinsic::umul_with_overflow:
              Res = LHS.umul_ov(RHS, Overflow);
              break;
            default:
              llvm_unreachable("Unexpected intrinsic ID");
            }
            return {Res, Overflow};
          });
    }
    case Intrinsic::sadd_sat:
    case Intrinsic::uadd_sat:
    case Intrinsic::ssub_sat:
    case Intrinsic::usub_sat:
    case Intrinsic::sshl_sat:
    case Intrinsic::ushl_sat: {
      return visitIntBinOpWithResult(
          RetTy, Args[0], Args[1],
          [IID](const APInt &LHS, const APInt &RHS) -> AnyValue {
            switch (IID) {
            case Intrinsic::sadd_sat:
              return LHS.sadd_sat(RHS);
            case Intrinsic::uadd_sat:
              return LHS.uadd_sat(RHS);
            case Intrinsic::ssub_sat:
              return LHS.ssub_sat(RHS);
            case Intrinsic::usub_sat:
              return LHS.usub_sat(RHS);
            case Intrinsic::sshl_sat: {
              if (RHS.uge(LHS.getBitWidth()))
                return AnyValue::poison();
              return LHS.sshl_sat(RHS);
            }
            case Intrinsic::ushl_sat: {
              if (RHS.uge(LHS.getBitWidth()))
                return AnyValue::poison();
              return LHS.ushl_sat(RHS);
            }
            default:
              llvm_unreachable("Unexpected intrinsic ID");
            }
          });
    }
    case Intrinsic::vector_reduce_add:
    case Intrinsic::vector_reduce_mul:
    case Intrinsic::vector_reduce_and:
    case Intrinsic::vector_reduce_or:
    case Intrinsic::vector_reduce_xor:
    case Intrinsic::vector_reduce_smax:
    case Intrinsic::vector_reduce_smin:
    case Intrinsic::vector_reduce_umax:
    case Intrinsic::vector_reduce_umin: {
      std::optional<APInt> Res;
      for (const auto &V : Args[0].asAggregate()) {
        if (V.isPoison()) {
          Res.reset();
          break;
        }
        const auto &IntV = V.asInteger();
        if (!Res) {
          Res = IntV;
          continue;
        }
        switch (IID) {
        case Intrinsic::vector_reduce_add:
          *Res += IntV;
          break;
        case Intrinsic::vector_reduce_mul:
          *Res *= IntV;
          break;
        case Intrinsic::vector_reduce_and:
          *Res &= IntV;
          break;
        case Intrinsic::vector_reduce_or:
          *Res |= IntV;
          break;
        case Intrinsic::vector_reduce_xor:
          *Res ^= IntV;
          break;
        case Intrinsic::vector_reduce_smax:
          *Res = APIntOps::smax(*Res, IntV);
          break;
        case Intrinsic::vector_reduce_smin:
          *Res = APIntOps::smin(*Res, IntV);
          break;
        case Intrinsic::vector_reduce_umax:
          *Res = APIntOps::umax(*Res, IntV);
          break;
        case Intrinsic::vector_reduce_umin:
          *Res = APIntOps::umin(*Res, IntV);
          break;
        default:
          llvm_unreachable("Unexpected intrinsic ID");
        }
      }
      return Res ? *Res : AnyValue::poison();
    }
    case Intrinsic::vector_insert: {
      if (Args[2].isPoison())
        return AnyValue::getPoisonValue(Ctx, RetTy);
      const auto &Vec = Args[0].asAggregate();
      const auto &SubVec = Args[1].asAggregate();
      const auto &Idx = Args[2].asInteger();
      auto EC =
          cast<VectorType>(CB.getArgOperand(1)->getType())->getElementCount();
      const uint64_t RawOffset = Idx.getZExtValue();
      const uint32_t MinSize = EC.getKnownMinValue();
      if (RawOffset % MinSize != 0)
        return AnyValue::getPoisonValue(Ctx, RetTy);
      const uint64_t Chunk = RawOffset / MinSize;
      const uint64_t EVL = Ctx.getEVL(EC);
      if (Chunk > std::numeric_limits<uint64_t>::max() / EVL)
        return AnyValue::getPoisonValue(Ctx, RetTy);
      const uint64_t Offset = Chunk * EVL;
      if (Offset > Vec.size() || SubVec.size() > Vec.size() - Offset)
        return AnyValue::getPoisonValue(Ctx, RetTy);
      std::vector<AnyValue> Res;
      Res.reserve(Vec.size());
      for (size_t I = 0; I != Vec.size(); ++I) {
        if (I >= Offset && I < Offset + SubVec.size())
          Res.push_back(SubVec[I - Offset]);
        else
          Res.push_back(Vec[I]);
      }
      return std::move(Res);
    }
    case Intrinsic::vector_extract: {
      if (Args[1].isPoison())
        return AnyValue::getPoisonValue(Ctx, RetTy);
      const auto &Vec = Args[0].asAggregate();
      const auto &Idx = Args[1].asInteger();
      auto EC = cast<VectorType>(RetTy)->getElementCount();
      const uint64_t RawOffset = Idx.getZExtValue();
      const uint32_t MinSize = EC.getKnownMinValue();
      if (RawOffset % MinSize != 0)
        return AnyValue::getPoisonValue(Ctx, RetTy);
      const uint64_t Chunk = RawOffset / MinSize;
      const uint64_t EVL = Ctx.getEVL(EC);
      if (Chunk > std::numeric_limits<uint64_t>::max() / EVL)
        return AnyValue::getPoisonValue(Ctx, RetTy);
      const uint64_t Offset = Chunk * EVL;
      if (Offset > Vec.size() || EVL > Vec.size() - Offset)
        return AnyValue::getPoisonValue(Ctx, RetTy);
      return std::vector<AnyValue>(Vec.begin() + Offset,
                                   Vec.begin() + Offset + EVL);
    }
    case Intrinsic::vector_reverse: {
      auto Vec = Args[0].asAggregate();
      std::reverse(Vec.begin(), Vec.end());
      return std::move(Vec);
    }
    case Intrinsic::vector_deinterleave2:
    case Intrinsic::vector_deinterleave3:
    case Intrinsic::vector_deinterleave4:
    case Intrinsic::vector_deinterleave5:
    case Intrinsic::vector_deinterleave6:
    case Intrinsic::vector_deinterleave7:
    case Intrinsic::vector_deinterleave8: {
      const unsigned Factor = getDeinterleaveIntrinsicFactor(IID);
      if (Factor == 0)
        llvm_unreachable("Unexpected intrinsic ID");
      const auto &Vec = Args[0].asAggregate();
      std::vector<std::vector<AnyValue>> Res(Factor);
      for (auto &SubVec : Res)
        SubVec.reserve(Vec.size() / Factor);
      for (size_t I = 0, E = Vec.size(); I != E; ++I)
        Res[I % Factor].push_back(Vec[I]);

      std::vector<AnyValue> AggRes;
      AggRes.reserve(Factor);
      for (auto &SubVec : Res)
        AggRes.emplace_back(std::move(SubVec));
      return AnyValue(std::move(AggRes));
    }
    case Intrinsic::vector_interleave2:
    case Intrinsic::vector_interleave3:
    case Intrinsic::vector_interleave4:
    case Intrinsic::vector_interleave5:
    case Intrinsic::vector_interleave6:
    case Intrinsic::vector_interleave7:
    case Intrinsic::vector_interleave8: {
      const unsigned Factor = getInterleaveIntrinsicFactor(IID);
      if (Factor == 0)
        llvm_unreachable("Unexpected intrinsic ID");
      const auto &Vec = Args[0].asAggregate();
      std::vector<AnyValue> Res;
      Res.reserve(Vec.size() * Factor);
      for (size_t I = 0, E = Vec.size(); I != E; ++I) {
        for (unsigned J = 0; J != Factor; ++J)
          Res.push_back(Args[J].asAggregate()[I]);
      }
      return std::move(Res);
    }
    case Intrinsic::vector_splice_left: {
      if (Args[2].isPoison())
        return AnyValue::getPoisonValue(Ctx, RetTy);
      const auto &LHS = Args[0].asAggregate();
      const auto &RHS = Args[1].asAggregate();
      const auto &Off = Args[2].asInteger();
      const size_t Len = LHS.size();
      if (Off.ugt(Len))
        return AnyValue::getPoisonValue(Ctx, RetTy);
      uint64_t Offset = Off.getZExtValue();
      std::vector<AnyValue> Res;
      Res.reserve(Len);
      for (size_t I = 0; I != Len; ++I) {
        size_t Pos = I + Offset;
        Res.push_back(Pos < Len ? LHS[Pos] : RHS[Pos - Len]);
      }
      return std::move(Res);
    }
    case Intrinsic::vector_splice_right: {
      if (Args[2].isPoison())
        return AnyValue::getPoisonValue(Ctx, RetTy);
      const auto &LHS = Args[0].asAggregate();
      const auto &RHS = Args[1].asAggregate();
      const auto &Off = Args[2].asInteger();
      const size_t Len = LHS.size();
      if (Off.ugt(Len))
        return AnyValue::getPoisonValue(Ctx, RetTy);
      uint64_t Offset = Len - Off.getZExtValue();
      std::vector<AnyValue> Res;
      Res.reserve(Len);
      for (size_t I = 0; I != Len; ++I) {
        size_t Pos = I + Offset;
        Res.push_back(Pos < Len ? LHS[Pos] : RHS[Pos - Len]);
      }
      return std::move(Res);
    }
    case Intrinsic::stepvector: {
      std::vector<AnyValue> Res;
      const uint32_t Len =
          Ctx.getEVL(cast<VectorType>(RetTy)->getElementCount());
      const unsigned BitWidth = RetTy->getScalarSizeInBits();
      Res.reserve(Len);
      for (uint64_t I = 0; I != Len; ++I) {
        Res.push_back(
            APInt(BitWidth, I, /*IsSigned=*/false, /*ImplicitTrunc=*/true));
      }
      return std::move(Res);
    }
    case Intrinsic::vector_reduce_fadd:
    case Intrinsic::vector_reduce_fmul:
    case Intrinsic::vector_reduce_fmaximum:
    case Intrinsic::vector_reduce_fminimum: {
      const auto DenormMode = getCurrentDenormalMode(RetTy);
      const bool HasStart = IID == Intrinsic::vector_reduce_fadd ||
                            IID == Intrinsic::vector_reduce_fmul;
      const AnyValue &Vector = HasStart ? Args[1] : Args[0];
      std::optional<APFloat> Res;
      if (HasStart) {
        if (Args[0].isPoison())
          return AnyValue::poison();
        const AnyValue ValidatedStart =
            handleFMFFlags(Args[0], FMF, /*IsInput=*/true);
        if (ValidatedStart.isPoison())
          return AnyValue::poison();
        Res = handleDenormal(ValidatedStart.asFloat(), DenormMode.Input,
                             /*IsInput=*/true);
      }
      for (const auto &V : Vector.asAggregate()) {
        if (V.isPoison())
          return AnyValue::poison();
        const AnyValue ValidatedOp = handleFMFFlags(V, FMF, /*IsInput=*/true);
        if (ValidatedOp.isPoison())
          return AnyValue::poison();
        APFloat Op = handleDenormal(ValidatedOp.asFloat(), DenormMode.Input,
                                    /*IsInput=*/true);
        if (!Res) {
          Res = std::move(Op);
          continue;
        }
        switch (IID) {
        case Intrinsic::vector_reduce_fadd:
          *Res = *Res + Op;
          break;
        case Intrinsic::vector_reduce_fmul:
          *Res = *Res * Op;
          break;
        case Intrinsic::vector_reduce_fmaximum:
          *Res = maximum(*Res, Op);
          break;
        case Intrinsic::vector_reduce_fminimum:
          *Res = minimum(*Res, Op);
          break;
        default:
          llvm_unreachable("Unexpected intrinsic ID");
        }
      }
      assert(Res.has_value());
      const AnyValue ValidatedRes =
          handleFMFFlags(*Res, FMF, /*IsInput=*/false);
      if (ValidatedRes.isPoison())
        return AnyValue::poison();
      const APFloat FRes =
          handleDenormal(ValidatedRes.asFloat(), DenormMode.Output,
                         /*IsInput=*/false);
      SmallVector<const APFloat *, 8> InputVec;
      InputVec.reserve(Vector.asAggregate().size());
      transform(
          Vector.asAggregate(), std::back_inserter(InputVec),
          [](const AnyValue &V) -> const APFloat * { return &V.asFloat(); });
      return applyNaNPropagation(FRes, InputVec);
    }
    case Intrinsic::vector_reduce_fmax:
    case Intrinsic::vector_reduce_fmin: {
      const auto DenormMode = getCurrentDenormalMode(RetTy);
      const auto &Vector = Args[0].asAggregate();
      SmallVector<APFloat, 8> InputFloats;
      SmallVector<const APFloat *, 8> InputVec;
      InputFloats.reserve(Vector.size());
      InputVec.reserve(Vector.size());
      for (const auto &V : Vector) {
        if (V.isPoison())
          return AnyValue::poison();
        const AnyValue ValidatedOp = handleFMFFlags(V, FMF, /*IsInput=*/true);
        if (ValidatedOp.isPoison())
          return AnyValue::poison();
        InputFloats.push_back(handleDenormal(ValidatedOp.asFloat(),
                                             DenormMode.Input,
                                             /*IsInput=*/true));
        InputVec.push_back(&InputFloats.back());
      }
      assert(!InputVec.empty());
      SmallVector<APFloat, 8> Worklist(InputFloats);
      const bool HasSNaN =
          any_of(InputVec, [](const APFloat *V) { return V->isSignaling(); });
      while (Worklist.size() > 1) {
        size_t LHSIdx = 0;
        size_t RHSIdx = 1;
        if (HasSNaN) {
          LHSIdx = Ctx.getRandomUInt64() % Worklist.size();
          RHSIdx = Ctx.getRandomUInt64() % (Worklist.size() - 1);
          if (RHSIdx >= LHSIdx)
            ++RHSIdx;
        }

        APFloat Res =
            IID == Intrinsic::vector_reduce_fmax
                ? maxnumWithSNaNQuieting(Worklist[LHSIdx], Worklist[RHSIdx])
                : minnumWithSNaNQuieting(Worklist[LHSIdx], Worklist[RHSIdx]);
        if (LHSIdx < RHSIdx)
          std::swap(LHSIdx, RHSIdx);
        Worklist.erase(Worklist.begin() + LHSIdx);
        Worklist.erase(Worklist.begin() + RHSIdx);
        Worklist.push_back(std::move(Res));
      }

      AnyValue ValidatedRes =
          handleFMFFlags(Worklist.front(), FMF, /*IsInput=*/false);
      if (ValidatedRes.isPoison())
        return AnyValue::poison();
      APFloat FRes = handleDenormal(ValidatedRes.asFloat(), DenormMode.Output,
                                    /*IsInput=*/false);

      return applyNaNPropagation(FRes, InputVec);
    }
    case Intrinsic::fabs: {
      return visitBitwiseFPUnOpWithResult(
          RetTy, FMF, Args[0],
          [](const APFloat &Operand) -> APFloat { return abs(Operand); });
    }
    case Intrinsic::fma: {
      return visitFPTriOpWithResult(
          RetTy, FMF, Args[0], Args[1], Args[2],
          [](const APFloat &Op1, const APFloat &Op2,
             const APFloat &Op3) -> APFloat {
            auto Res = Op1;
            Res.fusedMultiplyAdd(Op2, Op3, RoundingMode::NearestTiesToEven);
            return Res;
          });
    }
    case Intrinsic::fmuladd: {
      return visitFPTriOpWithResult(
          RetTy, FMF, Args[0], Args[1], Args[2],
          [&](const APFloat &Op1, const APFloat &Op2,
              const APFloat &Op3) -> APFloat {
            if (Ctx.fuseMultiplyAdd()) {
              auto Res = Op1;
              Res.fusedMultiplyAdd(Op2, Op3, RoundingMode::NearestTiesToEven);
              return Res;
            }
            return Op1 * Op2 + Op3;
          });
    }
    case Intrinsic::is_fpclass: {
      const FPClassTest Mask =
          static_cast<FPClassTest>(Args[1].asInteger().getZExtValue());
      return computeUnOp(RetTy, Args[0], [&](const AnyValue &Op) -> AnyValue {
        if (Op.isPoison())
          return AnyValue::poison();
        return AnyValue::boolean(
            static_cast<bool>(Op.asFloat().classify() & Mask));
      });
    }
    case Intrinsic::copysign: {
      return computeBinOp(
          RetTy, Args[0], Args[1],
          [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
            if (LHS.isPoison() || RHS.isPoison())
              return AnyValue::poison();
            const AnyValue ValidatedLHS =
                handleFMFFlags(LHS, FMF, /*IsInput=*/true);
            const AnyValue ValidatedRHS =
                handleFMFFlags(RHS, FMF, /*IsInput=*/true);
            if (ValidatedLHS.isPoison() || ValidatedRHS.isPoison())
              return AnyValue::poison();

            return handleFMFFlags(APFloat::copySign(ValidatedLHS.asFloat(),
                                                    ValidatedRHS.asFloat()),
                                  FMF, /*IsInput=*/false);
          });
    }
    case Intrinsic::maxnum:
    case Intrinsic::minnum:
    case Intrinsic::maximum:
    case Intrinsic::minimum:
    case Intrinsic::maximumnum:
    case Intrinsic::minimumnum: {
      return visitFPBinOpWithResult(
          RetTy, FMF, Args[0], Args[1],
          [&](const APFloat &LHS, const APFloat &RHS) -> APFloat {
            switch (IID) {
            case Intrinsic::maximum:
              return maximum(LHS, RHS);
            case Intrinsic::minimum:
              return minimum(LHS, RHS);
            case Intrinsic::maximumnum:
              return maximumnum(LHS, RHS);
            case Intrinsic::minimumnum:
              return minimumnum(LHS, RHS);
            case Intrinsic::maxnum:
              return maxnumWithSNaNQuieting(LHS, RHS);
            case Intrinsic::minnum:
              return minnumWithSNaNQuieting(LHS, RHS);
            default:
              llvm_unreachable("Unexpected intrinsic ID");
            }
          });
    }
    case Intrinsic::fptosi_sat:
    case Intrinsic::fptoui_sat: {
      const auto BitWidth = RetTy->getScalarSizeInBits();
      return computeUnOp(RetTy, Args[0], [&](const AnyValue &Op) -> AnyValue {
        if (Op.isPoison())
          return AnyValue::poison();
        const APFloat &Operand = Op.asFloat();
        APSInt V(BitWidth, IID == Intrinsic::fptoui_sat);
        [[maybe_unused]] bool IsExact;
        Operand.convertToInteger(V, APFloat::rmTowardZero, &IsExact);
        return V;
      });
    }
    default:
      Handler.onUnrecognizedInstruction(CB);
      setFailed();
      return AnyValue();
    }
  }

  AnyValue callLibFunc(CallBase &CB, Function *ResolvedCallee,
                       ArrayRef<AnyValue> CalleeArgs) {
    LibFunc LF;
    // Respect nobuiltin attributes on call site.
    if (CB.isNoBuiltin() ||
        !CurrentFrame->TLI.getLibFunc(*ResolvedCallee, LF)) {
      Handler.onUnrecognizedInstruction(CB);
      setFailed();
      return AnyValue();
    }

    if (auto LibCallRes =
            Lib.executeLibcall(LF, CB.getName(), CB.getType(), CalleeArgs))
      return *LibCallRes;

    if (ExitInfo)
      return AnyValue();

    Handler.onUnrecognizedInstruction(CB);
    setFailed();
    return AnyValue();
  }

  /// Handle both poison-generating and UB-implying attributes for parameters
  /// and return values.
  void handleAttributes(Type *Ty, AnyValue &V, AttributeSet AttrsAtCallSite,
                        AttributeSet AttrsAtCallee) {
    if (Ty->isIntOrIntVectorTy()) {
      if (auto CRAttr = AttrsAtCallSite.getAttribute(Attribute::Range);
          CRAttr.isValid())
        applyRangeAttr(V, CRAttr.getRange());
      if (auto CRAttr = AttrsAtCallee.getAttribute(Attribute::Range);
          CRAttr.isValid())
        applyRangeAttr(V, CRAttr.getRange());
    }
    if (AttributeFuncs::isNoFPClassCompatibleType(Ty)) {
      if (auto CRAttr = AttrsAtCallSite.getAttribute(Attribute::NoFPClass);
          CRAttr.isValid())
        applyNoFPClassAttr(V, CRAttr.getNoFPClass());
      if (auto CRAttr = AttrsAtCallee.getAttribute(Attribute::NoFPClass);
          CRAttr.isValid())
        applyNoFPClassAttr(V, CRAttr.getNoFPClass());
    }
    if (Ty->isPointerTy()) {
      if (AttrsAtCallSite.hasAttribute(Attribute::NonNull) ||
          AttrsAtCallee.hasAttribute(Attribute::NonNull))
        applyNonNullAttr(V, Ty->getPointerAddressSpace(), DL);
    }
    if (Ty->isPtrOrPtrVectorTy()) {
      if (MaybeAlign Align = AttrsAtCallSite.getAlignment())
        applyAlignAttr(V, *Align);
      if (MaybeAlign Align = AttrsAtCallee.getAlignment())
        applyAlignAttr(V, *Align);
    }
    if ((AttrsAtCallSite.hasAttribute(Attribute::NoUndef) ||
         AttrsAtCallee.hasAttribute(Attribute::NoUndef)) &&
        violatesNoUndefAttr(V)) {
      reportImmediateUB() << "The value " << V
                          << " violates noundef attribute.";
      return;
    }
    if (Ty->isPointerTy()) {
      unsigned AS = Ty->getPointerAddressSpace();
      if (uint64_t DereferenceableBytes =
              std::max(AttrsAtCallSite.getDereferenceableBytes(),
                       AttrsAtCallee.getDereferenceableBytes())) {
        if (violatesDereferenceableBytesAttr(V, DereferenceableBytes,
                                             /*OrNull=*/false, AS, DL))
          reportImmediateUB()
              << "The value " << V << " violates dereferenceable("
              << DereferenceableBytes << ") attribute.";
      } else if (uint64_t DereferenceableOrNullBytes =
                     std::max(AttrsAtCallSite.getDereferenceableOrNullBytes(),
                              AttrsAtCallee.getDereferenceableOrNullBytes())) {
        if (violatesDereferenceableBytesAttr(V, DereferenceableOrNullBytes,
                                             /*OrNull=*/true, AS, DL))
          reportImmediateUB() << "The value " << V
                              << " violates "
                                 "dereferenceable_or_null("
                              << DereferenceableOrNullBytes << ") attribute.";
      }
    }
  }

  /// Handle both poison-generating and UB-implying metadata on instructions.
  void handleMetadata(Type *Ty, AnyValue &V, Instruction &I) {
    auto ExtractFirstIntOperand = [](const MDNode *Node) {
      return mdconst::extract<ConstantInt>(Node->getOperand(0))->getZExtValue();
    };

    if (Ty->isIntOrIntVectorTy()) {
      if (MDNode *Ranges = I.getMetadata(LLVMContext::MD_range)) {
        SmallVector<ConstantRange> RangeList;
        for (uint32_t I = 0; I < Ranges->getNumOperands(); I += 2) {
          RangeList.emplace_back(
              mdconst::extract<ConstantInt>(Ranges->getOperand(I))->getValue(),
              mdconst::extract<ConstantInt>(Ranges->getOperand(I + 1))
                  ->getValue());
        }
        forEachScalarValue(V, [&](AnyValue &Scalar) {
          if (!Scalar.isInteger())
            return;
          for (auto &CR : RangeList)
            if (CR.contains(Scalar.asInteger()))
              return;
          Scalar = AnyValue::poison();
        });
      }
    }
    if (AttributeFuncs::isNoFPClassCompatibleType(Ty)) {
      if (const MDNode *NoFPClass = I.getMetadata(LLVMContext::MD_nofpclass)) {
        applyNoFPClassAttr(
            V, static_cast<FPClassTest>(ExtractFirstIntOperand(NoFPClass)));
      }
    }
    if (Ty->isPointerTy()) {
      if (I.hasMetadata(LLVMContext::MD_nonnull))
        applyNonNullAttr(V, Ty->getPointerAddressSpace(), DL);
      // Unlike align attributes, !align is only defined for pointer types.
      if (const MDNode *Alignment = I.getMetadata(LLVMContext::MD_align))
        applyAlignAttr(V, Align(ExtractFirstIntOperand(Alignment)));
    }
    if (I.hasMetadata(LLVMContext::MD_noundef) && violatesNoUndefAttr(V)) {
      reportImmediateUB() << "The value " << V
                          << " violates !noundef metadata.";
      return;
    }
    if (Ty->isPointerTy()) {
      unsigned AS = Ty->getPointerAddressSpace();
      if (const MDNode *DereferenceableBytes =
              I.getMetadata(LLVMContext::MD_dereferenceable)) {
        uint64_t Bytes = ExtractFirstIntOperand(DereferenceableBytes);
        if (violatesDereferenceableBytesAttr(V, Bytes,
                                             /*OrNull=*/false, AS, DL))
          reportImmediateUB()
              << "The value " << V << " violates !dereferenceable !{i64 "
              << Bytes << "} metadata.";
      } else if (const MDNode *DereferenceableOrNullBytes =
                     I.getMetadata(LLVMContext::MD_dereferenceable_or_null)) {
        uint64_t Bytes = ExtractFirstIntOperand(DereferenceableOrNullBytes);
        if (violatesDereferenceableBytesAttr(V, Bytes,
                                             /*OrNull=*/true, AS, DL))
          reportImmediateUB()
              << "The value " << V << " violates !dereferenceable_or_null!{i64 "
              << Bytes << "} metadata.";
      }
    }
  }

  void enterCall(CallBase &CB) {
    Function *Callee = CB.getCalledFunction();
    // TODO: handle byval/initializes
    auto &CalleeArgs = CurrentFrame->CalleeArgs;
    assert(CalleeArgs.empty() &&
           "Forgot to call returnFromCallee before entering a new call.");
    for (Value *Arg : CB.args())
      CalleeArgs.push_back(getValue(Arg));

    if (!Callee) {
      Value *CalledOperand = CB.getCalledOperand();
      if (isNoopInlineAsm(CalledOperand, CB.getType())) {
        CurrentFrame->ResolvedCallee = nullptr;
        returnFromCallee();
        return;
      }

      if (isa<InlineAsm>(CalledOperand)) {
        Handler.onUnrecognizedInstruction(CB);
        setFailed();
        return;
      }

      auto &CalleeVal = getValue(CalledOperand);
      if (CalleeVal.isPoison()) {
        reportImmediateUB() << "Indirect call through poison function pointer.";
        return;
      }
      Callee = Ctx.getTargetFunction(CalleeVal.asPointer());
      if (!Callee) {
        reportImmediateUB()
            << "Indirect call through invalid function pointer.";
        return;
      }
      if (Callee->getFunctionType() != CB.getFunctionType()) {
        reportImmediateUB() << "Indirect call through a function pointer with "
                               "mismatched signature. Expected: "
                            << *CB.getFunctionType()
                            << ", Actual: " << *Callee->getFunctionType();
        return;
      }
    }

    assert(Callee && "Expected a resolved callee function.");
    assert(
        Callee->getFunctionType() == CB.getFunctionType() &&
        "Expected the callee function type to match the call site signature.");

    // Handle parameter attributes (Attributes from resolved callee should be
    // applied if available).
    for (auto [I, Arg] : enumerate(CB.args())) {
      Type *ArgTy = Arg->getType();
      AnyValue &ArgVal = CalleeArgs[I];
      // CallBase::paramHasAttr also checks parameter attributes at known
      // callee. We do it explicitly to avoid duplication.
      AttributeSet AttrsAtCallSite = CB.getParamAttributes(I);
      AttributeSet AttrsAtCallee = Callee->getAttributes().getParamAttrs(I);
      handleAttributes(ArgTy, ArgVal, AttrsAtCallSite, AttrsAtCallee);
    }

    CurrentFrame->ResolvedCallee = Callee;
    if (Callee->isIntrinsic()) {
      CurrentFrame->CalleeRetVal = callIntrinsic(CB, CalleeArgs);
      returnFromCallee();
      return;
    } else if (Callee->isDeclaration()) {
      CurrentFrame->CalleeRetVal = callLibFunc(CB, Callee, CalleeArgs);
      returnFromCallee();
      return;
    } else {
      uint32_t MaxStackDepth = Ctx.getMaxStackDepth();
      if (MaxStackDepth && CallStack.size() >= MaxStackDepth) {
        reportError() << "Maximum stack depth exceeded.";
        return;
      }
      assert(!Callee->empty() && "Expected a defined function.");
      // Suspend the current frame and push the callee frame onto the stack.
      ArrayRef<AnyValue> Args = CurrentFrame->CalleeArgs;
      AnyValue &RetVal = CurrentFrame->CalleeRetVal;
      CurrentFrame->State = FrameState::Pending;
      CallStack.emplace_back(*Callee, &CB, CurrentFrame, Args, RetVal,
                             Ctx.getTLIImpl());
    }
  }

  void visitCallInst(CallInst &CI) { enterCall(CI); }

  void visitInvokeInst(InvokeInst &II) {
    // TODO: handle exceptions
    enterCall(II);
  }

  void visitAdd(BinaryOperator &I) {
    visitIntBinOp(I, [&](const APInt &LHS, const APInt &RHS) {
      return addNoWrap(LHS, RHS, I.hasNoSignedWrap(), I.hasNoUnsignedWrap());
    });
  }

  void visitSub(BinaryOperator &I) {
    visitIntBinOp(I, [&](const APInt &LHS, const APInt &RHS) {
      return subNoWrap(LHS, RHS, I.hasNoSignedWrap(), I.hasNoUnsignedWrap());
    });
  }

  void visitMul(BinaryOperator &I) {
    visitIntBinOp(I, [&](const APInt &LHS, const APInt &RHS) {
      return mulNoWrap(LHS, RHS, I.hasNoSignedWrap(), I.hasNoUnsignedWrap());
    });
  }

  void visitSDiv(BinaryOperator &I) {
    visitBinOp(I, [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
      // Priority: Immediate UB > poison > normal value
      if (RHS.isPoison()) {
        reportImmediateUB() << "Division by zero (refine RHS to 0).";
        return AnyValue::poison();
      }
      const APInt &RHSVal = RHS.asInteger();
      if (RHSVal.isZero()) {
        reportImmediateUB() << "Division by zero.";
        return AnyValue::poison();
      }
      if (LHS.isPoison()) {
        if (RHSVal.isAllOnes())
          reportImmediateUB()
              << "Signed division overflow (refine LHS to INT_MIN).";
        return AnyValue::poison();
      }
      const APInt &LHSVal = LHS.asInteger();
      if (LHSVal.isMinSignedValue() && RHSVal.isAllOnes()) {
        reportImmediateUB() << "Signed division overflow.";
        return AnyValue::poison();
      }

      if (I.isExact()) {
        APInt Q, R;
        APInt::sdivrem(LHSVal, RHSVal, Q, R);
        if (!R.isZero())
          return AnyValue::poison();
        return Q;
      } else {
        return LHSVal.sdiv(RHSVal);
      }
    });
  }

  void visitSRem(BinaryOperator &I) {
    visitBinOp(I, [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
      // Priority: Immediate UB > poison > normal value
      if (RHS.isPoison()) {
        reportImmediateUB() << "Division by zero (refine RHS to 0).";
        return AnyValue::poison();
      }
      const APInt &RHSVal = RHS.asInteger();
      if (RHSVal.isZero()) {
        reportImmediateUB() << "Division by zero.";
        return AnyValue::poison();
      }
      if (LHS.isPoison()) {
        if (RHSVal.isAllOnes())
          reportImmediateUB()
              << "Signed division overflow (refine LHS to INT_MIN).";
        return AnyValue::poison();
      }
      const APInt &LHSVal = LHS.asInteger();
      if (LHSVal.isMinSignedValue() && RHSVal.isAllOnes()) {
        reportImmediateUB() << "Signed division overflow. LHS: " << LHSVal
                            << ", RHS: " << RHSVal;
        return AnyValue::poison();
      }

      return LHSVal.srem(RHSVal);
    });
  }

  void visitUDiv(BinaryOperator &I) {
    visitBinOp(I, [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
      // Priority: Immediate UB > poison > normal value
      if (RHS.isPoison()) {
        reportImmediateUB() << "Division by zero (refine RHS to 0).";
        return AnyValue::poison();
      }
      const APInt &RHSVal = RHS.asInteger();
      if (RHSVal.isZero()) {
        reportImmediateUB() << "Division by zero.";
        return AnyValue::poison();
      }
      if (LHS.isPoison())
        return AnyValue::poison();
      const APInt &LHSVal = LHS.asInteger();

      if (I.isExact()) {
        APInt Q, R;
        APInt::udivrem(LHSVal, RHSVal, Q, R);
        if (!R.isZero())
          return AnyValue::poison();
        return Q;
      } else {
        return LHSVal.udiv(RHSVal);
      }
    });
  }

  void visitURem(BinaryOperator &I) {
    visitBinOp(I, [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
      // Priority: Immediate UB > poison > normal value
      if (RHS.isPoison()) {
        reportImmediateUB() << "Division by zero (refine RHS to 0).";
        return AnyValue::poison();
      }
      const APInt &RHSVal = RHS.asInteger();
      if (RHSVal.isZero()) {
        reportImmediateUB() << "Division by zero.";
        return AnyValue::poison();
      }
      if (LHS.isPoison())
        return AnyValue::poison();
      const APInt &LHSVal = LHS.asInteger();
      return LHSVal.urem(RHSVal);
    });
  }

  void visitFAdd(BinaryOperator &I) {
    visitFPBinOp(I, [](const APFloat &LHS, const APFloat &RHS) -> APFloat {
      APFloat Res = LHS;
      Res.add(RHS, APFloat::rmNearestTiesToEven);
      return Res;
    });
  }

  void visitFSub(BinaryOperator &I) {
    visitFPBinOp(I, [](const APFloat &LHS, const APFloat &RHS) -> APFloat {
      APFloat Res = LHS;
      Res.subtract(RHS, APFloat::rmNearestTiesToEven);
      return Res;
    });
  }

  void visitFMul(BinaryOperator &I) {
    visitFPBinOp(I, [](const APFloat &LHS, const APFloat &RHS) -> APFloat {
      APFloat Res = LHS;
      Res.multiply(RHS, APFloat::rmNearestTiesToEven);
      return Res;
    });
  }

  void visitFDiv(BinaryOperator &I) {
    visitFPBinOp(I, [](const APFloat &LHS, const APFloat &RHS) -> APFloat {
      APFloat Res = LHS;
      Res.divide(RHS, APFloat::rmNearestTiesToEven);
      return Res;
    });
  }

  void visitFRem(BinaryOperator &I) {
    visitFPBinOp(I, [](const APFloat &LHS, const APFloat &RHS) -> APFloat {
      APFloat Res = LHS;
      Res.mod(RHS);
      return Res;
    });
  }

  void visitFNeg(UnaryOperator &I) {
    visitBitwiseFPUnOp(
        I, [](const APFloat &Operand) -> APFloat { return -Operand; });
  }

  void visitTruncInst(TruncInst &Trunc) {
    visitIntUnOp(Trunc, [&](const APInt &Operand) -> AnyValue {
      unsigned DestBW = Trunc.getType()->getScalarSizeInBits();
      if (Trunc.hasNoSignedWrap() && Operand.getSignificantBits() > DestBW)
        return AnyValue::poison();
      if (Trunc.hasNoUnsignedWrap() && Operand.getActiveBits() > DestBW)
        return AnyValue::poison();
      return Operand.trunc(DestBW);
    });
  }

  void visitZExtInst(ZExtInst &ZExt) {
    visitIntUnOp(ZExt, [&](const APInt &Operand) -> AnyValue {
      uint32_t DestBW = ZExt.getDestTy()->getScalarSizeInBits();
      if (ZExt.hasNonNeg() && Operand.isNegative())
        return AnyValue::poison();
      return Operand.zext(DestBW);
    });
  }

  void visitSExtInst(SExtInst &SExt) {
    visitIntUnOp(SExt, [&](const APInt &Operand) -> AnyValue {
      uint32_t DestBW = SExt.getDestTy()->getScalarSizeInBits();
      return Operand.sext(DestBW);
    });
  }

  void visitFPExtInst(FPExtInst &FPExt) { visitFPConvInst(FPExt); }

  void visitFPTruncInst(FPTruncInst &FPTrunc) { visitFPConvInst(FPTrunc); }

  void visitFPConvInst(Instruction &I) {
    if (!Ctx.isDefaultFPEnv())
      reportImmediateUB() << "Non-constrained floating-point operation assumes "
                             "default floating-point environment";

    const fltSemantics &DstSem =
        I.getType()->getScalarType()->getFltSemantics();

    visitUnOp(I, [&](const AnyValue &Operand) -> AnyValue {
      if (Operand.isPoison())
        return AnyValue::poison();

      FastMathFlags FMF = cast<FPMathOperator>(I).getFastMathFlags();
      DenormalMode DenormMode =
          getCurrentDenormalMode(I.getOperand(0)->getType());

      auto ValidatedOperand = handleFMFFlags(Operand, FMF, /*IsInput=*/true);
      if (ValidatedOperand.isPoison())
        return ValidatedOperand;

      APFloat FOperand = handleDenormal(ValidatedOperand.asFloat(),
                                        DenormMode.Input, /*IsInput=*/true);
      APFloat SourceNaN = FOperand;

      bool LosesInfo;
      FOperand.convert(DstSem, Ctx.getCurrentRoundingMode(), &LosesInfo);

      if (auto ValidateRes = handleFMFFlags(FOperand, FMF, /*IsInput=*/false);
          ValidateRes.isPoison())
        return ValidateRes;

      FOperand = handleDenormal(std::move(FOperand), DenormMode.Output, true);

      return AnyValue(applyNaNPropagation(FOperand, {&SourceNaN}));
    });
  }

  void visitFPToSIInst(FPToSIInst &FPToSI) {
    visitFPToIntInst(FPToSI, /*IsUnsigned=*/false);
  }

  void visitFPToUIInst(FPToUIInst &FPToUI) {
    visitFPToIntInst(FPToUI, /*IsUnsigned=*/true);
  }

  void visitFPToIntInst(Instruction &I, bool IsUnsigned) {
    // Note: We DO NOT use CurrentRoundingMode here.
    // Language specs require truncation towards zero for FP-to-Int conversions.
    visitUnOp(I, [&](const AnyValue &Operand) -> AnyValue {
      if (Operand.isPoison())
        return AnyValue::poison();

      APSInt Res(I.getType()->getScalarSizeInBits(), /*isUnsigned=*/IsUnsigned);
      bool IsExact;
      APFloat::opStatus Status = Operand.asFloat().convertToInteger(
          Res, APFloat::rmTowardZero, &IsExact);

      if (Status == APFloat::opInvalidOp)
        return AnyValue::poison();

      return AnyValue(Res);
    });
  }

  void visitSIToFPInst(SIToFPInst &SIToFP) {
    visitIntToFPInst(SIToFP, /*IsSigned=*/true);
  }

  void visitUIToFPInst(UIToFPInst &UIToFP) {
    visitIntToFPInst(UIToFP, /*IsSigned=*/false);
  }

  void visitIntToFPInst(Instruction &I, bool IsSigned) {
    const fltSemantics &DstSem =
        I.getType()->getScalarType()->getFltSemantics();

    visitUnOp(I, [&](const AnyValue &Operand) -> AnyValue {
      if (Operand.isPoison())
        return AnyValue::poison();

      APInt IOperand = Operand.asInteger();

      if (isa<UIToFPInst>(I) && I.hasNonNeg() && IOperand.isNegative())
        return AnyValue::poison();

      APFloat Res(DstSem);

      Res.convertFromAPInt(Operand.asInteger(), /*IsSigned=*/IsSigned,
                           Ctx.getCurrentRoundingMode());

      return AnyValue(Res);
    });
  }

  void visitAnd(BinaryOperator &I) {
    visitIntBinOp(I, [](const APInt &LHS, const APInt &RHS) -> AnyValue {
      return LHS & RHS;
    });
  }

  void visitXor(BinaryOperator &I) {
    visitIntBinOp(I, [](const APInt &LHS, const APInt &RHS) -> AnyValue {
      return LHS ^ RHS;
    });
  }

  void visitOr(BinaryOperator &I) {
    visitIntBinOp(I, [&](const APInt &LHS, const APInt &RHS) -> AnyValue {
      if (cast<PossiblyDisjointInst>(I).isDisjoint() && LHS.intersects(RHS))
        return AnyValue::poison();
      return LHS | RHS;
    });
  }

  void visitShl(BinaryOperator &I) {
    visitIntBinOp(I, [&](const APInt &LHS, const APInt &RHS) -> AnyValue {
      if (RHS.uge(LHS.getBitWidth()))
        return AnyValue::poison();
      if (I.hasNoSignedWrap() && RHS.uge(LHS.getNumSignBits()))
        return AnyValue::poison();
      if (I.hasNoUnsignedWrap() && RHS.ugt(LHS.countl_zero()))
        return AnyValue::poison();
      return LHS.shl(RHS);
    });
  }

  void visitLShr(BinaryOperator &I) {
    visitIntBinOp(I, [&](const APInt &LHS, const APInt &RHS) -> AnyValue {
      if (RHS.uge(LHS.getBitWidth()) ||
          (cast<PossiblyExactOperator>(I).isExact() &&
           RHS.ugt(LHS.countr_zero())))
        return AnyValue::poison();
      return LHS.lshr(RHS);
    });
  }

  void visitAShr(BinaryOperator &I) {
    visitIntBinOp(I, [&](const APInt &LHS, const APInt &RHS) -> AnyValue {
      if (RHS.uge(LHS.getBitWidth()) ||
          (cast<PossiblyExactOperator>(I).isExact() &&
           RHS.ugt(LHS.countr_zero())))
        return AnyValue::poison();
      return LHS.ashr(RHS);
    });
  }

  void visitICmpInst(ICmpInst &I) {
    visitBinOp(I, [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
      if (LHS.isPoison() || RHS.isPoison())
        return AnyValue::poison();
      // TODO: handle pointer comparison.
      const APInt &LHSVal = LHS.asInteger();
      const APInt &RHSVal = RHS.asInteger();
      if (I.hasSameSign() && LHSVal.isNonNegative() != RHSVal.isNonNegative())
        return AnyValue::poison();
      return AnyValue::boolean(
          ICmpInst::compare(LHSVal, RHSVal, I.getPredicate()));
    });
  }

  void visitFCmpInst(FCmpInst &I) {
    DenormalMode DenormMode =
        getCurrentDenormalMode(I.getOperand(0)->getType());
    FastMathFlags FMF = I.getFastMathFlags();

    visitBinOp(I, [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
      if (LHS.isPoison() || RHS.isPoison())
        return AnyValue::poison();

      if (auto ValidateRes = handleFMFFlags(LHS, FMF, /*IsInput=*/true);
          ValidateRes.isPoison())
        return ValidateRes;
      if (auto ValidateRes = handleFMFFlags(RHS, FMF, /*IsInput=*/true);
          ValidateRes.isPoison())
        return ValidateRes;

      APFloat FLHS =
          handleDenormal(LHS.asFloat(), DenormMode.Input, /*IsInput=*/true);
      APFloat FRHS =
          handleDenormal(RHS.asFloat(), DenormMode.Input, /*IsInput=*/true);

      return AnyValue::boolean(FCmpInst::compare(FLHS, FRHS, I.getPredicate()));
    });
  }

  void visitSelect(SelectInst &SI) {
    AnyValue Res;

    if (SI.getCondition()->getType()->isIntegerTy(1)) {
      switch (getValue(SI.getCondition()).asBoolean()) {
      case BooleanKind::True:
        Res = getValue(SI.getTrueValue());
        break;
      case BooleanKind::False:
        Res = getValue(SI.getFalseValue());
        break;
      case BooleanKind::Poison:
        Res = AnyValue::getPoisonValue(Ctx, SI.getType());
        break;
      }
    } else {
      auto &Cond = getValue(SI.getCondition()).asAggregate();
      auto &TV = getValue(SI.getTrueValue()).asAggregate();
      auto &FV = getValue(SI.getFalseValue()).asAggregate();
      std::vector<AnyValue> ResVec;
      size_t Len = Cond.size();
      ResVec.reserve(Len);
      for (uint32_t I = 0; I != Len; ++I) {
        switch (Cond[I].asBoolean()) {
        case BooleanKind::True:
          ResVec.push_back(TV[I]);
          break;
        case BooleanKind::False:
          ResVec.push_back(FV[I]);
          break;
        case BooleanKind::Poison:
          ResVec.push_back(AnyValue::poison());
          break;
        }
      }
      Res = AnyValue(std::move(ResVec));
    }

    // Handle fast-math flags
    if (auto *FPMO = dyn_cast<FPMathOperator>(&SI)) {
      if (FastMathFlags FMF = FPMO->getFastMathFlags(); FMF.any())
        Res = handleFMFFlags(std::move(Res), FMF, /*IsInput=*/true);
    }

    setResult(SI, std::move(Res));
  }

  void visitAllocaInst(AllocaInst &AI) {
    uint64_t AllocSize = Ctx.getEffectiveTypeAllocSize(AI.getAllocatedType());
    if (AI.isArrayAllocation()) {
      auto &Size = getValue(AI.getArraySize());
      if (Size.isPoison()) {
        reportImmediateUB() << "Alloca with poison array size.";
        return;
      }
      if (Size.asInteger().getActiveBits() > 64) {
        reportImmediateUB()
            << "Alloca with large array size that overflows uint64_t. Size: "
            << Size.asInteger();
        return;
      }
      bool Overflowed = false;
      AllocSize = SaturatingMultiply(AllocSize, Size.asInteger().getZExtValue(),
                                     &Overflowed);
      if (Overflowed) {
        reportImmediateUB()
            << "Alloca with allocation size that overflows uint64_t. Size: "
            << Size.asInteger();
        return;
      }
    }
    // If it is used by llvm.lifetime.start, it should be initially dead.
    bool IsInitiallyDead = any_of(AI.users(), [](User *U) {
      return match(U, m_Intrinsic<Intrinsic::lifetime_start>());
    });
    auto Obj = Ctx.allocate(AllocSize, AI.getPointerAlignment(DL).value(),
                            AI.getName(), AI.getAddressSpace(),
                            IsInitiallyDead ? MemInitKind::Poisoned
                                            : MemInitKind::Uninitialized,
                            MemAllocKind::Stack);
    if (!Obj) {
      reportError() << "Insufficient stack space.";
      return;
    }
    CurrentFrame->Allocas.push_back(Obj);
    setResult(AI, Ctx.deriveFromMemoryObject(Obj));
  }

  void visitGetElementPtrInst(GetElementPtrInst &GEP) {
    uint32_t IndexBitWidth =
        DL.getIndexSizeInBits(GEP.getType()->getPointerAddressSpace());
    GEPNoWrapFlags Flags = GEP.getNoWrapFlags();
    AnyValue Res = getValue(GEP.getPointerOperand());
    AnyValue AccumulatedOffset = APInt(IndexBitWidth, 0);
    if (Res.isAggregate())
      AccumulatedOffset =
          AnyValue::getVectorSplat(AccumulatedOffset, Res.asAggregate().size());
    auto ApplyScaledOffset = [&](const AnyValue &Index, const APInt &Scale) {
      if (Index.isAggregate() && !Res.isAggregate()) {
        Res = AnyValue::getVectorSplat(Res, Index.asAggregate().size());
        AccumulatedOffset = AnyValue::getVectorSplat(
            AccumulatedOffset, Index.asAggregate().size());
      }
      if (Index.isAggregate() && Res.isAggregate()) {
        for (auto &&[ResElem, IndexElem, OffsetElem] :
             zip(Res.asAggregate(), Index.asAggregate(),
                 AccumulatedOffset.asAggregate()))
          ResElem = computeScaledPtrAdd(
              ResElem, canonicalizeIndex(IndexElem, IndexBitWidth, Flags),
              Scale, Flags, OffsetElem);
      } else {
        AnyValue CanonicalIndex =
            canonicalizeIndex(Index, IndexBitWidth, Flags);
        if (Res.isAggregate()) {
          for (auto &&[ResElem, OffsetElem] :
               zip(Res.asAggregate(), AccumulatedOffset.asAggregate()))
            ResElem = computeScaledPtrAdd(ResElem, CanonicalIndex, Scale, Flags,
                                          OffsetElem);
        } else {
          Res = computeScaledPtrAdd(Res, CanonicalIndex, Scale, Flags,
                                    AccumulatedOffset);
        }
      }
    };

    for (gep_type_iterator GTI = gep_type_begin(GEP), GTE = gep_type_end(GEP);
         GTI != GTE; ++GTI) {
      Value *V = GTI.getOperand();

      // Fast path for zero offsets.
      if (auto *CI = dyn_cast<ConstantInt>(V)) {
        if (CI->isZero())
          continue;
      }
      if (isa<ConstantAggregateZero>(V))
        continue;

      // Handle a struct index, which adds its field offset to the pointer.
      if (StructType *STy = GTI.getStructTypeOrNull()) {
        unsigned ElementIdx = cast<ConstantInt>(V)->getZExtValue();
        const StructLayout *SL = DL.getStructLayout(STy);
        // Element offset is in bytes.
        ApplyScaledOffset(
            APInt(IndexBitWidth, SL->getElementOffset(ElementIdx)),
            APInt(IndexBitWidth, 1));
        continue;
      }

      // Truncate if type size exceeds index space.
      // TODO: Should be documented in LangRef: GEPs with nowrap flags should
      // return poison when the type size exceeds index space.
      TypeSize Offset = GTI.getSequentialElementStride(DL);
      APInt Scale(IndexBitWidth, Ctx.getEffectiveTypeSize(Offset),
                  /*isSigned=*/false, /*implicitTrunc=*/true);
      if (!Scale.isZero())
        ApplyScaledOffset(getValue(V), Scale);
    }

    setResult(GEP, std::move(Res));
  }

  void visitIntToPtr(IntToPtrInst &I) {
    return visitUnOp(I, [&](const AnyValue &V) -> AnyValue {
      if (V.isPoison())
        return AnyValue::poison();
      // TODO: expose provenance
      // TODO: check metadata
      return Pointer(V.asInteger().zextOrTrunc(
          DL.getPointerSizeInBits(I.getType()->getPointerAddressSpace())));
    });
  }

  void visitLoadInst(LoadInst &LI) {
    auto RetVal = load(getValue(LI.getPointerOperand()), LI.getAlign(),
                       LI.getType(), LI.hasMetadata(LLVMContext::MD_noundef));
    // TODO: track volatile loads
    handleMetadata(LI.getType(), RetVal, LI);
    setResult(LI, std::move(RetVal));
  }

  void visitStoreInst(StoreInst &SI) {
    auto &Ptr = getValue(SI.getPointerOperand());
    auto &Val = getValue(SI.getValueOperand());
    // TODO: track volatile stores
    // TODO: handle metadata
    store(Ptr, SI.getAlign(), Val, SI.getValueOperand()->getType());
    if (!hasProgramExited() && !Handler.onInstructionExecuted(SI, AnyValue()))
      setFailed();
  }

  void visitInstruction(Instruction &I) {
    Handler.onUnrecognizedInstruction(I);
    setFailed();
  }

  void visitExtractValueInst(ExtractValueInst &EVI) {
    auto &Res = getValue(EVI.getAggregateOperand());
    const AnyValue *Pos = &Res;
    for (unsigned Idx : EVI.indices())
      Pos = &Pos->asAggregate()[Idx];
    setResult(EVI, *Pos);
  }

  void visitInsertValueInst(InsertValueInst &IVI) {
    AnyValue Res = getValue(IVI.getAggregateOperand());
    AnyValue *Pos = &Res;
    for (unsigned Idx : IVI.indices())
      Pos = &Pos->asAggregate()[Idx];
    *Pos = getValue(IVI.getInsertedValueOperand());
    setResult(IVI, std::move(Res));
  }

  void visitInsertElementInst(InsertElementInst &IEI) {
    auto Res = getValue(IEI.getOperand(0));
    auto &ResVec = Res.asAggregate();
    auto &Idx = getValue(IEI.getOperand(2));
    if (Idx.isPoison() || Idx.asInteger().uge(ResVec.size())) {
      setResult(IEI, AnyValue::getPoisonValue(Ctx, IEI.getType()));
      return;
    }
    ResVec[Idx.asInteger().getZExtValue()] = getValue(IEI.getOperand(1));
    setResult(IEI, std::move(Res));
  }

  void visitExtractElementInst(ExtractElementInst &EEI) {
    auto &SrcVec = getValue(EEI.getOperand(0)).asAggregate();
    auto &Idx = getValue(EEI.getOperand(1));
    if (Idx.isPoison() || Idx.asInteger().uge(SrcVec.size())) {
      setResult(EEI, AnyValue::getPoisonValue(Ctx, EEI.getType()));
      return;
    }
    setResult(EEI, SrcVec[Idx.asInteger().getZExtValue()]);
  }

  void visitShuffleVectorInst(ShuffleVectorInst &SVI) {
    auto &LHSVec = getValue(SVI.getOperand(0)).asAggregate();
    auto &RHSVec = getValue(SVI.getOperand(1)).asAggregate();
    uint32_t Size = cast<VectorType>(SVI.getOperand(0)->getType())
                        ->getElementCount()
                        .getKnownMinValue();
    std::vector<AnyValue> Res;
    uint32_t DstLen = Ctx.getEVL(SVI.getType()->getElementCount());
    Res.reserve(DstLen);
    uint32_t Stride = SVI.getShuffleMask().size();
    // For scalable vectors, we need to repeat the shuffle mask until we fill
    // the destination vector.
    for (uint32_t Off = 0; Off != DstLen; Off += Stride) {
      for (int Idx : SVI.getShuffleMask()) {
        if (Idx == PoisonMaskElem)
          Res.push_back(AnyValue::poison());
        else if (Idx < static_cast<int>(Size))
          Res.push_back(LHSVec[Idx]);
        else
          Res.push_back(RHSVec[Idx - Size]);
      }
    }
    setResult(SVI, std::move(Res));
  }

  void visitBitCastInst(BitCastInst &BCI) {
    // The conversion is done as if the value had been stored to memory and read
    // back as the target type.
    SmallVector<Byte> Bytes;
    Bytes.resize(Ctx.getEffectiveTypeStoreSize(BCI.getType()),
                 Byte::concrete(0));
    Ctx.toBytes(getValue(BCI.getOperand(0)), BCI.getOperand(0)->getType(),
                Bytes);
    setResult(BCI, Ctx.fromBytes(Bytes, BCI.getType()));
  }

  void visitFreezeInst(FreezeInst &FI) {
    AnyValue Val = getValue(FI.getOperand(0));
    Ctx.freeze(Val, FI.getType());
    setResult(FI, std::move(Val));
  }

  /// This function implements the main interpreter loop.
  /// It handles function calls in a non-recursive manner to avoid stack
  /// overflows.
  ProgramExitInfo runMainLoop() {
    uint32_t MaxSteps = Ctx.getMaxSteps();
    uint32_t Steps = 0;
    while (!hasProgramExited() && !CallStack.empty()) {
      Frame &Top = CallStack.back();
      CurrentFrame = &Top;
      if (Top.State == FrameState::Entry) {
        Handler.onFunctionEntry(Top.Func, Top.Args, Top.CallSite);
      } else {
        assert(Top.State == FrameState::Pending &&
               "Expected to return from a callee.");
        returnFromCallee();
      }

      Top.State = FrameState::Running;
      // Interpreter loop inside a function
      while (!hasProgramExited()) {
        assert(Top.State == FrameState::Running &&
               "Expected to be in running state.");
        if (MaxSteps != 0 && Steps >= MaxSteps) {
          reportError() << "Exceeded maximum number of execution steps.";
          break;
        }
        ++Steps;

        Instruction &I = *Top.PC;
        visit(&I);
        if (hasProgramExited())
          break;

        // A function call or return has occurred.
        // We need to exit the inner loop and switch to a different frame.
        if (Top.State != FrameState::Running)
          break;

        // Otherwise, move to the next instruction if it is not a terminator.
        // For terminators, the PC is updated in the visit* method.
        if (!I.isTerminator())
          ++Top.PC;
      }

      if (hasProgramExited())
        break;

      if (Top.State == FrameState::Exit) {
        assert((Top.Func.getReturnType()->isVoidTy() || !Top.RetVal.isNone()) &&
               "Expected return value to be set on function exit.");
        Handler.onFunctionExit(Top.Func, Top.RetVal);
        // Free stack objects allocated in this frame.
        for (auto &Obj : Top.Allocas)
          Ctx.free(*Obj);
        CallStack.pop_back();
      } else {
        assert(Top.State == FrameState::Pending &&
               "Expected to enter a callee.");
      }
    }
    if (!hasProgramExited())
      requestProgramExit(ProgramExitInfo::ProgramExitKind::Returned);
    return *getExitInfo();
  }
};

ProgramExitInfo Context::runFunction(Function &F, ArrayRef<AnyValue> Args,
                                     AnyValue &RetVal, EventHandler &Handler) {
  InstExecutor Executor(*this, Handler, F, Args, RetVal);
  return Executor.runMainLoop();
}

} // namespace llvm::ubi