| //===- 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/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" |
| |
| 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; |
| } |
| |
| /// 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; |
| Library Lib; |
| |
| const AnyValue &getValue(Value *V) { |
| if (auto *C = dyn_cast<Constant>(V)) |
| return Ctx.getConstantValue(C); |
| return CurrentFrame->ValueMap.at(V); |
| } |
| |
| void setResult(Instruction &I, AnyValue V) { |
| if (!hasProgramExited() && !Handler.onInstructionExecuted(I, V)) |
| setFailed(); |
| CurrentFrame->ValueMap.insert_or_assign(&I, std::move(V)); |
| } |
| |
| 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()); |
| }); |
| } |
| |
| AnyValue |
| visitIntUnOpWithResult(Instruction &I, |
| function_ref<AnyValue(const APInt &)> ScalarFn) { |
| return computeUnOp(I.getType(), getValue(I.getOperand(0)), |
| [&](const AnyValue &Operand) -> AnyValue { |
| if (Operand.isPoison()) |
| return AnyValue::poison(); |
| return ScalarFn(Operand.asInteger()); |
| }); |
| } |
| |
| 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()); |
| }); |
| } |
| |
| AnyValue visitIntBinOpWithResult( |
| Instruction &I, |
| function_ref<AnyValue(const APInt &, const APInt &)> ScalarFn) { |
| return computeBinOp( |
| I.getType(), getValue(I.getOperand(0)), getValue(I.getOperand(1)), |
| [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue { |
| if (LHS.isPoison() || RHS.isPoison()) |
| return AnyValue::poison(); |
| return ScalarFn(LHS.asInteger(), RHS.asInteger()); |
| }); |
| } |
| |
| AnyValue visitOverflowIntBinOpWithResult( |
| CallBase &CB, |
| function_ref<std::pair<APInt, bool>(const APInt &, const APInt &)> |
| ScalarFn) { |
| const AnyValue &LHS = getValue(CB.getOperand(0)); |
| const AnyValue &RHS = getValue(CB.getOperand(1)); |
| if (!LHS.isAggregate()) { |
| if (LHS.isPoison() || RHS.isPoison()) |
| return std::vector{AnyValue::poison(), AnyValue::poison()}; |
| auto [Res, Overflow] = ScalarFn(LHS.asInteger(), RHS.asInteger()); |
| return std::vector{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(std::move(ResVec)), |
| AnyValue(std::move(OverflowVec))}; |
| } |
| |
| 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( |
| Instruction &I, |
| function_ref<AnyValue(const APInt &, const APInt &, const APInt &)> |
| ScalarFn) { |
| return computeTriOp( |
| I.getType(), getValue(I.getOperand(0)), getValue(I.getOperand(1)), |
| getValue(I.getOperand(2)), |
| [&](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()); |
| }); |
| } |
| |
| 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))) { |
| Value *Incoming = PHI->getIncomingValueForBlock(From); |
| // TODO: handle fast-math flags. |
| IncomingValues.emplace_back(PHI, getValue(Incoming)); |
| ++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); |
| } |
| |
| // 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; |
| } |
| |
| 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() { |
| // TODO: handle retval attributes (Attributes from known callee should be |
| // applied if available). |
| // TODO: handle metadata |
| auto &CB = cast<CallBase>(*CurrentFrame->PC); |
| CurrentFrame->CalleeArgs.clear(); |
| AnyValue &RetVal = CurrentFrame->CalleeRetVal; |
| 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(); |
| |
| switch (IID) { |
| case Intrinsic::assume: |
| switch (Args[0].asBoolean()) { |
| case BooleanKind::True: |
| break; |
| case BooleanKind::False: |
| case BooleanKind::Poison: |
| reportImmediateUB("Assume on false or poison condition."); |
| break; |
| } |
| // TODO: handle llvm.assume with operand bundles |
| 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(CB, [&](const APInt &Operand) -> AnyValue { |
| if (IsIntMinPoison && Operand.isMinSignedValue()) |
| return AnyValue::poison(); |
| return Operand.abs(); |
| }); |
| } |
| case Intrinsic::smax: { |
| return visitIntBinOpWithResult( |
| CB, [](const APInt &LHS, const APInt &RHS) -> AnyValue { |
| return APIntOps::smax(LHS, RHS); |
| }); |
| } |
| case Intrinsic::smin: { |
| return visitIntBinOpWithResult( |
| CB, [](const APInt &LHS, const APInt &RHS) -> AnyValue { |
| return APIntOps::smin(LHS, RHS); |
| }); |
| } |
| case Intrinsic::umax: { |
| return visitIntBinOpWithResult( |
| CB, [](const APInt &LHS, const APInt &RHS) -> AnyValue { |
| return APIntOps::umax(LHS, RHS); |
| }); |
| } |
| case Intrinsic::umin: { |
| return visitIntBinOpWithResult( |
| CB, [](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( |
| CB, [&](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(CB, [](const APInt &Operand) -> AnyValue { |
| return Operand.reverseBits(); |
| }); |
| } |
| case Intrinsic::bswap: { |
| return visitIntUnOpWithResult(CB, [](const APInt &Operand) -> AnyValue { |
| return Operand.byteSwap(); |
| }); |
| } |
| case Intrinsic::ctpop: { |
| return visitIntUnOpWithResult(CB, [](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(CB, [&](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( |
| CB, |
| [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( |
| CB, [](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( |
| CB, |
| [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( |
| CB, [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::poison(); |
| const auto &Vec = Args[0].asAggregate(); |
| const auto &SubVec = Args[1].asAggregate(); |
| const auto &Idx = Args[2].asInteger(); |
| const uint64_t Offset = Idx.getZExtValue(); |
| if (Offset + SubVec.size() > Vec.size()) |
| return AnyValue::poison(); |
| 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::poison(); |
| const auto &Vec = Args[0].asAggregate(); |
| const auto &Idx = Args[1].asInteger(); |
| const uint64_t Offset = Idx.getZExtValue(); |
| const uint64_t DstSize = |
| Ctx.getEVL(cast<VectorType>(RetTy)->getElementCount()); |
| if (Offset + DstSize > Vec.size()) |
| return AnyValue::poison(); |
| return std::vector(Vec.begin() + Offset, Vec.begin() + Offset + DstSize); |
| } |
| 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::poison(); |
| 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::poison(); |
| 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::poison(); |
| 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::poison(); |
| 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); |
| } |
| 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(); |
| } |
| |
| void enterCall(CallBase &CB) { |
| Function *Callee = CB.getCalledFunction(); |
| // TODO: handle parameter attributes (Attributes from known callee should be |
| // applied if available). |
| // 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."); |
| return; |
| } |
| } |
| |
| assert(Callee && "Expected a resolved callee function."); |
| assert( |
| Callee->getFunctionType() == CB.getFunctionType() && |
| "Expected the callee function type to match the call site signature."); |
| 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."); |
| 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 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 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(cast<PossiblyExactOperator>(I).isExact() |
| ? LHS.countr_zero() + 1 |
| : LHS.getBitWidth())) |
| return AnyValue::poison(); |
| return LHS.lshr(RHS); |
| }); |
| } |
| |
| void visitAShr(BinaryOperator &I) { |
| visitIntBinOp(I, [&](const APInt &LHS, const APInt &RHS) -> AnyValue { |
| if (RHS.uge(cast<PossiblyExactOperator>(I).isExact() |
| ? LHS.countr_zero() + 1 |
| : LHS.getBitWidth())) |
| 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 visitSelect(SelectInst &SI) { |
| // TODO: handle fast-math flags. |
| if (SI.getCondition()->getType()->isIntegerTy(1)) { |
| switch (getValue(SI.getCondition()).asBoolean()) { |
| case BooleanKind::True: |
| setResult(SI, getValue(SI.getTrueValue())); |
| return; |
| case BooleanKind::False: |
| setResult(SI, getValue(SI.getFalseValue())); |
| return; |
| case BooleanKind::Poison: |
| setResult(SI, AnyValue::getPoisonValue(Ctx, SI.getType())); |
| return; |
| } |
| } |
| |
| auto &Cond = getValue(SI.getCondition()).asAggregate(); |
| auto &TV = getValue(SI.getTrueValue()).asAggregate(); |
| auto &FV = getValue(SI.getFalseValue()).asAggregate(); |
| std::vector<AnyValue> Res; |
| size_t Len = Cond.size(); |
| Res.reserve(Len); |
| for (uint32_t I = 0; I != Len; ++I) { |
| switch (Cond[I].asBoolean()) { |
| case BooleanKind::True: |
| Res.push_back(TV[I]); |
| break; |
| case BooleanKind::False: |
| Res.push_back(FV[I]); |
| break; |
| case BooleanKind::Poison: |
| Res.push_back(AnyValue::poison()); |
| break; |
| } |
| } |
| 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."); |
| return; |
| } |
| bool Overflowed = false; |
| AllocSize = SaturatingMultiply(AllocSize, Size.asInteger().getZExtValue(), |
| &Overflowed); |
| if (Overflowed) { |
| reportImmediateUB( |
| "Alloca with allocation size that overflows uint64_t."); |
| 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()); |
| // TODO: track volatile loads |
| // TODO: handle metadata |
| 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 |
