1//===- Interpreter.cpp - Interpreter Loop for llubi -----------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements the evaluation loop for each kind of instruction.
10//
11//===----------------------------------------------------------------------===//
12
13#include "Context.h"
14#include "ExecutorBase.h"
15#include "Library.h"
16#include "Value.h"
17#include "llvm/ADT/STLExtras.h"
18#include "llvm/ADT/SmallVector.h"
19#include "llvm/Analysis/VectorUtils.h"
20#include "llvm/IR/InlineAsm.h"
21#include "llvm/IR/InstVisitor.h"
22#include "llvm/IR/Intrinsics.h"
23#include "llvm/IR/Operator.h"
24#include "llvm/IR/PatternMatch.h"
25#include "llvm/Support/Allocator.h"
26#include "llvm/TargetParser/Triple.h"
27
28#include <cassert>
29#include <cstring>
30#include <limits>
31
32namespace llvm::ubi {
33
34using namespace PatternMatch;
35
36/// Visit the scalar values recursively. The callback function may modify the
37/// value in-place.
38static void forEachScalarValue(AnyValue &V,
39 function_ref<void(AnyValue &)> Visit) {
40 if (V.isNone())
41 return;
42
43 if (V.isAggregate()) {
44 for (auto &SubValue : V.asAggregate())
45 forEachScalarValue(V&: SubValue, Visit);
46 return;
47 }
48
49 Visit(V);
50}
51
52static void applyRangeAttr(AnyValue &V, const ConstantRange &CR) {
53 forEachScalarValue(V, Visit: [&](AnyValue &Scalar) {
54 if (Scalar.isInteger() && !CR.contains(Val: Scalar.asInteger()))
55 Scalar = AnyValue::poison();
56 });
57}
58
59static void applyNoFPClassAttr(AnyValue &V, FPClassTest NoFPClass) {
60 forEachScalarValue(V, Visit: [NoFPClass](AnyValue &Scalar) {
61 if (Scalar.isFloat() && (Scalar.asFloat().classify() & NoFPClass))
62 Scalar = AnyValue::poison();
63 });
64}
65
66static void applyNonNullAttr(AnyValue &V, unsigned AS, const DataLayout &DL) {
67 if (V.isPointer() && V.asPointer().isNullPtr(AS, DL))
68 V = AnyValue::poison();
69}
70
71static void applyAlignAttr(AnyValue &V, Align Alignment) {
72 forEachScalarValue(V, Visit: [Alignment](AnyValue &Scalar) {
73 if (Scalar.isPointer() &&
74 Scalar.asPointer().address().countr_zero() < Log2(A: Alignment))
75 Scalar = AnyValue::poison();
76 });
77}
78
79static bool violatesNoUndefAttr(AnyValue &V) {
80 bool ContainsPoison = false;
81 forEachScalarValue(V, Visit: [&](AnyValue &Scalar) {
82 if (Scalar.isPoison()) {
83 ContainsPoison = true;
84 return;
85 }
86 if (Scalar.isByte() && !ContainsPoison) {
87 // For non-byte-sized values, high bits are always zeroed out.
88 ContainsPoison = any_of(Range: Scalar.asByte().bytes(), P: [](const Byte &V) {
89 return V.ConcreteMask != 255;
90 });
91 }
92 });
93 return ContainsPoison;
94}
95
96/// Assumes V is either a poison or a pointer.
97static bool violatesDereferenceableBytesAttr(const AnyValue &V, uint64_t Bytes,
98 bool OrNull, unsigned AS,
99 Context &Ctx) {
100 if (V.isPoison())
101 return true;
102
103 auto &Ptr = V.asPointer();
104 if (Ptr.isNullPtr(AS, DL: Ctx.getDataLayout())) {
105 if (OrNull)
106 return false;
107 return true;
108 }
109
110 auto *MO = Ctx.checkProvenance(Ptr, Check: [&](const Provenance &) {
111 // TODO: check read_provenance
112 // TODO: check nofree for attributes/metadata.
113 return true;
114 });
115 if (!MO)
116 return true;
117
118 const APInt &PtrAddr = Ptr.address();
119 return Bytes > MO->getSize() || PtrAddr.ult(RHS: MO->getAddress()) ||
120 PtrAddr.ugt(RHS: MO->getAddress() + MO->getSize() - Bytes);
121}
122
123/// Instruction executor using the visitor pattern.
124/// Unlike the Context class that manages the global state,
125/// InstExecutor only maintains the state for call frames.
126class InstExecutor : public InstVisitor<InstExecutor, void>,
127 public ExecutorBase {
128 const DataLayout &DL;
129 std::list<Frame> CallStack;
130 AnyValue None;
131 std::list<AnyValue> UnsupportedConstantValues;
132 Library Lib;
133
134 const AnyValue &getValue(Value *V) {
135 if (auto *C = dyn_cast<Constant>(Val: V)) {
136 if (const AnyValue *Val = Ctx.getConstantValue(C))
137 return *Val;
138 reportError() << "Unsupported constant: " << *C << ".";
139 UnsupportedConstantValues.push_back(
140 x: AnyValue::getPoisonValue(Ctx, Ty: C->getType()));
141 return UnsupportedConstantValues.back();
142 }
143 if (isa<MetadataAsValue>(Val: V))
144 return None;
145 return CurrentFrame->ValueMap.at(Val: V);
146 }
147
148 void setResult(Instruction &I, AnyValue V) {
149 if (!hasProgramExited() && !Handler.onInstructionExecuted(I, Result: V))
150 setFailed();
151 if (hasProgramExited())
152 return;
153 assert(V.isCompatibleWith(I.getType()) && "Unexpected value storage kind.");
154 if (!V.isNone())
155 CurrentFrame->ValueMap.insert_or_assign(Key: &I, Val: std::move(V));
156 }
157
158 APFloat handleDenormal(APFloat Val, DenormalMode::DenormalModeKind Mode,
159 bool IsInput) {
160 if (!Val.isDenormal())
161 return Val;
162 if (IsInput) {
163 // Non-deterministically choose between flushing or preserving the
164 // denormal value.
165 if (Ctx.getRandomBool())
166 return Val;
167 }
168 if (Mode == DenormalMode::PositiveZero)
169 return APFloat::getZero(Sem: Val.getSemantics(), Negative: false);
170 if (Mode == DenormalMode::PreserveSign)
171 return APFloat::getZero(Sem: Val.getSemantics(), Negative: Val.isNegative());
172 // Default case for IEEE, Dynamic, and Invalid
173 // Currently we treat Dynamic the same as IEEE, since we don't support
174 // changing the mode at this point.
175 return Val;
176 }
177
178 AnyValue handleFMFFlags(AnyValue Val, FastMathFlags FMF, bool IsInput) {
179 if (Val.isPoison())
180 return AnyValue::poison();
181
182 if (Val.isAggregate()) {
183 std::vector<AnyValue> ResVec;
184 ResVec.reserve(n: Val.asAggregate().size());
185 for (const auto &A : Val.asAggregate())
186 ResVec.push_back(x: handleFMFFlags(Val: A, FMF, IsInput));
187 return AnyValue(ResVec);
188 }
189
190 const APFloat &APVal = Val.asFloat();
191 if (FMF.noNaNs() && APVal.isNaN())
192 return AnyValue::poison();
193 if (FMF.noInfs() && APVal.isInfinity())
194 return AnyValue::poison();
195 if (IsInput && FMF.noSignedZeros() && APVal.isZero())
196 return AnyValue(APFloat::getZero(
197 Sem: APVal.getSemantics(), Negative: APVal.isNegative() ^ Ctx.getRandomBool()));
198 return Val;
199 }
200
201 void addNaNCandidate(SmallVectorImpl<APFloat> &Candidates,
202 APFloat Candidate) {
203 if (any_of(Range&: Candidates, P: [&](const APFloat &Existing) {
204 return Existing.bitwiseIsEqual(RHS: Candidate);
205 }))
206 return;
207 Candidates.push_back(Elt: std::move(Candidate));
208 }
209
210 APFloat pickNaNCandidate(ArrayRef<APFloat> Candidates) {
211 assert(!Candidates.empty() && "Need at least one NaN candidate.");
212 return Candidates[Ctx.getRandomUInt64() % Candidates.size()];
213 }
214
215 APInt getRandomNaNPayload(const fltSemantics &Sem) {
216 const unsigned NumBits = Sem.precision - 1;
217 SmallVector<APInt::WordType, 2> RandomWords;
218 const unsigned NumWords = APInt::getNumWords(BitWidth: NumBits);
219 RandomWords.reserve(N: NumWords);
220 for (unsigned I = 0; I != NumWords; ++I)
221 RandomWords.push_back(Elt: Ctx.getRandomUInt64());
222 return APInt(NumBits, RandomWords);
223 }
224
225 bool isPreferredNaN(const APFloat &Val) {
226 assert(Val.isNaN() && "Expected NaN.");
227 const APFloat Preferred =
228 APFloat::getQNaN(Sem: Val.getSemantics(), Negative: Val.isNegative());
229 return Val.bitwiseIsEqual(RHS: Preferred);
230 }
231
232 bool wasmMayProduceExtraNaNPayload(ArrayRef<const APFloat *> Inputs) {
233 for (const APFloat *Input : Inputs) {
234 if (!Input->isNaN())
235 continue;
236 if (Input->isSignaling() || !isPreferredNaN(Val: *Input))
237 return true;
238 }
239 return false;
240 }
241
242 APFloat propagateInputNaN(const APFloat &InputNaN, const fltSemantics &DstSem,
243 bool QuietingMode, bool FlipSign) {
244 APFloat Res = InputNaN;
245 bool LosesInfo;
246 Res.convert(ToSemantics: DstSem, RM: APFloat::rmNearestTiesToEven, losesInfo: &LosesInfo);
247 if (FlipSign)
248 Res.changeSign();
249 if (QuietingMode && Res.isSignaling())
250 Res = Res.makeQuiet();
251 return Res;
252 }
253
254 APFloat maybeQuietSNaN(APFloat Val) const {
255 if (Val.isSignaling() && Ctx.getRandomBool())
256 return Val.makeQuiet();
257 return Val;
258 }
259
260 APFloat maxnumWithSNaNQuieting(const APFloat &LHS, const APFloat &RHS) {
261 return maxnum(A: maybeQuietSNaN(Val: LHS), B: maybeQuietSNaN(Val: RHS));
262 }
263
264 APFloat minnumWithSNaNQuieting(const APFloat &LHS, const APFloat &RHS) {
265 return minnum(A: maybeQuietSNaN(Val: LHS), B: maybeQuietSNaN(Val: RHS));
266 }
267
268 void addPropagatedNaNCandidates(SmallVectorImpl<APFloat> &Candidates,
269 ArrayRef<const APFloat *> Inputs,
270 const fltSemantics &DstSem, bool QuietingMode,
271 bool SignChoice) {
272 for (const APFloat *Input : Inputs) {
273 if (!Input->isNaN())
274 continue;
275 addNaNCandidate(Candidates, Candidate: propagateInputNaN(InputNaN: *Input, DstSem,
276 QuietingMode, FlipSign: SignChoice));
277 }
278 }
279
280 void addTargetSpecificNaNCandidates(SmallVectorImpl<APFloat> &Candidates,
281 const APFloat &Result,
282 ArrayRef<const APFloat *> Inputs,
283 bool SignChoice) {
284 const Triple &TT = Ctx.getTargetTriple();
285 if (TT.isWasm()) {
286 if (!wasmMayProduceExtraNaNPayload(Inputs))
287 return;
288 APInt Payload = getRandomNaNPayload(Sem: Result.getSemantics());
289 addNaNCandidate(Candidates, Candidate: APFloat::getQNaN(Sem: Result.getSemantics(),
290 Negative: SignChoice, payload: &Payload));
291 return;
292 }
293
294 if (TT.isSPARC32() || TT.isSPARC64()) {
295 APInt Payload = APInt::getAllOnes(numBits: Result.getSemantics().precision - 1);
296 addNaNCandidate(Candidates, Candidate: APFloat::getQNaN(Sem: Result.getSemantics(),
297 Negative: SignChoice, payload: &Payload));
298 }
299 }
300
301 APFloat applyNaNPropagation(const APFloat &Result,
302 ArrayRef<const APFloat *> Inputs) {
303 if (!Result.isNaN())
304 return Result;
305
306 const NaNPropagationBehavior Choice =
307 Ctx.getEffectiveNaNPropagationBehavior();
308 const bool SignChoice = Ctx.getRandomBool();
309 const fltSemantics &ResultSem = Result.getSemantics();
310 auto PreferredNaN = [&]() {
311 return APFloat::getQNaN(Sem: ResultSem, Negative: SignChoice);
312 };
313
314 SmallVector<APFloat, 4> Candidates;
315 switch (Choice) {
316 case NaNPropagationBehavior::PreferredNaN:
317 return PreferredNaN();
318 case NaNPropagationBehavior::QuietingNaN:
319 addPropagatedNaNCandidates(Candidates, Inputs, DstSem: ResultSem,
320 /*QuietingMode=*/true, SignChoice);
321 return Candidates.empty() ? PreferredNaN() : pickNaNCandidate(Candidates);
322 case NaNPropagationBehavior::UnchangedNaN:
323 addPropagatedNaNCandidates(Candidates, Inputs, DstSem: ResultSem,
324 /*QuietingMode=*/false, SignChoice);
325 return Candidates.empty() ? PreferredNaN() : pickNaNCandidate(Candidates);
326 case NaNPropagationBehavior::TargetSpecificNaN:
327 addTargetSpecificNaNCandidates(Candidates, Result, Inputs, SignChoice);
328 return Candidates.empty() ? PreferredNaN() : pickNaNCandidate(Candidates);
329 case NaNPropagationBehavior::NonDeterministic:
330 addNaNCandidate(Candidates, Candidate: PreferredNaN());
331 addPropagatedNaNCandidates(Candidates, Inputs, DstSem: ResultSem,
332 /*QuietingMode=*/true, SignChoice);
333 addPropagatedNaNCandidates(Candidates, Inputs, DstSem: ResultSem,
334 /*QuietingMode=*/false, SignChoice);
335 addTargetSpecificNaNCandidates(Candidates, Result, Inputs, SignChoice);
336 return pickNaNCandidate(Candidates);
337 }
338 llvm_unreachable("Unhandled NaN propagation behavior.");
339 }
340
341 AnyValue computeUnOp(Type *Ty, const AnyValue &Operand,
342 function_ref<AnyValue(const AnyValue &)> ScalarFn) {
343 if (Ty->isVectorTy()) {
344 auto &OperandVec = Operand.asAggregate();
345 std::vector<AnyValue> ResVec;
346 ResVec.reserve(n: OperandVec.size());
347 for (const auto &Scalar : OperandVec)
348 ResVec.push_back(x: ScalarFn(Scalar));
349 return std::move(ResVec);
350 }
351 return ScalarFn(Operand);
352 }
353
354 void visitUnOp(Instruction &I,
355 function_ref<AnyValue(const AnyValue &)> ScalarFn) {
356 setResult(I, V: computeUnOp(Ty: I.getType(), Operand: getValue(V: I.getOperand(i: 0)), ScalarFn));
357 }
358
359 void visitIntUnOp(Instruction &I,
360 function_ref<AnyValue(const APInt &)> ScalarFn) {
361 visitUnOp(I, ScalarFn: [&](const AnyValue &Operand) -> AnyValue {
362 if (Operand.isPoison())
363 return AnyValue::poison();
364 return ScalarFn(Operand.asInteger());
365 });
366 }
367
368 void visitBitwiseFPUnOp(Instruction &I,
369 function_ref<APFloat(const APFloat &)> ScalarFn) {
370 setResult(I, V: visitBitwiseFPUnOpWithResult(
371 RetTy: I.getType(), FMF: cast<FPMathOperator>(Val&: I).getFastMathFlags(),
372 Operand: getValue(V: I.getOperand(i: 0)), ScalarFn));
373 }
374
375 AnyValue
376 visitIntUnOpWithResult(Type *RetTy, const AnyValue &Operand,
377 function_ref<AnyValue(const APInt &)> ScalarFn) {
378 return computeUnOp(Ty: RetTy, Operand,
379 ScalarFn: [&](const AnyValue &OperandInner) -> AnyValue {
380 if (OperandInner.isPoison())
381 return AnyValue::poison();
382 return ScalarFn(OperandInner.asInteger());
383 });
384 }
385
386 AnyValue visitBitwiseFPUnOpWithResult(
387 Type *RetTy, const FastMathFlags &FMF, const AnyValue &Operand,
388 function_ref<APFloat(const APFloat &)> ScalarFn) {
389 return computeUnOp(
390 Ty: RetTy, Operand, ScalarFn: [&](const AnyValue &OperandInner) -> AnyValue {
391 if (OperandInner.isPoison())
392 return AnyValue::poison();
393
394 // We don't flush denormals here since bitwise floating-point
395 // operations only manipulate on certain bits of the operand.
396
397 AnyValue ValidatedOperand =
398 handleFMFFlags(Val: OperandInner, FMF, /*IsInput=*/true);
399 if (ValidatedOperand.isPoison())
400 return ValidatedOperand;
401
402 APFloat Result = ScalarFn(ValidatedOperand.asFloat());
403
404 return handleFMFFlags(Val: Result, FMF, /*IsInput=*/false);
405 });
406 }
407
408 AnyValue computeBinOp(
409 Type *Ty, const AnyValue &LHS, const AnyValue &RHS,
410 function_ref<AnyValue(const AnyValue &, const AnyValue &)> ScalarFn) {
411 if (Ty->isVectorTy()) {
412 auto &LHSVec = LHS.asAggregate();
413 auto &RHSVec = RHS.asAggregate();
414 std::vector<AnyValue> ResVec;
415 ResVec.reserve(n: LHSVec.size());
416 for (const auto &[ScalarLHS, ScalarRHS] : zip(t: LHSVec, u: RHSVec))
417 ResVec.push_back(x: ScalarFn(ScalarLHS, ScalarRHS));
418 return std::move(ResVec);
419 }
420 return ScalarFn(LHS, RHS);
421 }
422
423 void visitBinOp(
424 Instruction &I,
425 function_ref<AnyValue(const AnyValue &, const AnyValue &)> ScalarFn) {
426 setResult(I, V: computeBinOp(Ty: I.getType(), LHS: getValue(V: I.getOperand(i: 0)),
427 RHS: getValue(V: I.getOperand(i: 1)), ScalarFn));
428 }
429
430 void
431 visitIntBinOp(Instruction &I,
432 function_ref<AnyValue(const APInt &, const APInt &)> ScalarFn) {
433 visitBinOp(I, ScalarFn: [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
434 if (LHS.isPoison() || RHS.isPoison())
435 return AnyValue::poison();
436 return ScalarFn(LHS.asInteger(), RHS.asInteger());
437 });
438 }
439
440 void visitFPBinOp(
441 Instruction &I,
442 function_ref<APFloat(const APFloat &, const APFloat &)> ScalarFn) {
443 setResult(I, V: visitFPBinOpWithResult(
444 RetTy: I.getType(), FMF: cast<FPMathOperator>(Val&: I).getFastMathFlags(),
445 LHS: getValue(V: I.getOperand(i: 0)), RHS: getValue(V: I.getOperand(i: 1)),
446 ScalarFn));
447 }
448
449 AnyValue visitIntBinOpWithResult(
450 Type *RetTy, const AnyValue &LHS, const AnyValue &RHS,
451 function_ref<AnyValue(const APInt &, const APInt &)> ScalarFn) {
452 return computeBinOp(
453 Ty: RetTy, LHS, RHS,
454 ScalarFn: [&](const AnyValue &LHSInner, const AnyValue &RHSInner) -> AnyValue {
455 if (LHSInner.isPoison() || RHSInner.isPoison())
456 return AnyValue::poison();
457 return ScalarFn(LHSInner.asInteger(), RHSInner.asInteger());
458 });
459 }
460
461 AnyValue visitOverflowIntBinOpWithResult(
462 Type *RetTy, const AnyValue &LHS, const AnyValue &RHS,
463 function_ref<std::pair<APInt, bool>(const APInt &, const APInt &)>
464 ScalarFn) {
465 if (!LHS.isAggregate()) {
466 if (LHS.isPoison() || RHS.isPoison())
467 return std::vector<AnyValue>{AnyValue::poison(), AnyValue::poison()};
468 auto [Res, Overflow] = ScalarFn(LHS.asInteger(), RHS.asInteger());
469 return std::vector<AnyValue>{AnyValue(Res), AnyValue::boolean(Val: Overflow)};
470 }
471
472 auto &LHSVec = LHS.asAggregate();
473 auto &RHSVec = RHS.asAggregate();
474 std::vector<AnyValue> ResVec;
475 std::vector<AnyValue> OverflowVec;
476 ResVec.reserve(n: LHSVec.size());
477 OverflowVec.reserve(n: LHSVec.size());
478 for (const auto &[ScalarLHS, ScalarRHS] : zip(t: LHSVec, u: RHSVec)) {
479 if (ScalarLHS.isPoison() || ScalarRHS.isPoison()) {
480 ResVec.push_back(x: AnyValue::poison());
481 OverflowVec.push_back(x: AnyValue::poison());
482 continue;
483 }
484 auto [Res, Overflow] =
485 ScalarFn(ScalarLHS.asInteger(), ScalarRHS.asInteger());
486 ResVec.push_back(x: AnyValue(Res));
487 OverflowVec.push_back(x: AnyValue::boolean(Val: Overflow));
488 }
489 return std::vector<AnyValue>{AnyValue(std::move(ResVec)),
490 AnyValue(std::move(OverflowVec))};
491 }
492
493 AnyValue visitFPBinOpWithResult(
494 Type *RetTy, const FastMathFlags &FMF, const AnyValue &LHS,
495 const AnyValue &RHS,
496 function_ref<APFloat(const APFloat &, const APFloat &)> ScalarFn) {
497 DenormalMode DenormMode = getCurrentDenormalMode(Ty: RetTy);
498
499 if (!Ctx.isDefaultFPEnv())
500 reportImmediateUB() << "Non-constrained floating-point operation assumes "
501 "default floating-point environment";
502
503 return computeBinOp(
504 Ty: RetTy, LHS, RHS,
505 ScalarFn: [&](const AnyValue &LHSInner, const AnyValue &RHSInner) -> AnyValue {
506 if (LHSInner.isPoison() || RHSInner.isPoison())
507 return AnyValue::poison();
508
509 AnyValue ValidatedLHS =
510 handleFMFFlags(Val: LHSInner, FMF, /*IsInput=*/true);
511 AnyValue ValidatedRHS =
512 handleFMFFlags(Val: RHSInner, FMF, /*IsInput=*/true);
513 if (ValidatedLHS.isPoison())
514 return ValidatedLHS;
515 if (ValidatedRHS.isPoison())
516 return ValidatedRHS;
517
518 // Flush input denormals
519 APFloat FLHS = handleDenormal(Val: ValidatedLHS.asFloat(),
520 Mode: DenormMode.Input, /*IsInput=*/true);
521 APFloat FRHS = handleDenormal(Val: ValidatedRHS.asFloat(),
522 Mode: DenormMode.Input, /*IsInput=*/true);
523
524 APFloat RawResult = ScalarFn(FLHS, FRHS);
525
526 // Flush output denormals and handle fast-math flags.
527 AnyValue FResult = handleFMFFlags(
528 Val: handleDenormal(Val: RawResult, Mode: DenormMode.Output, /*IsInput=*/false),
529 FMF,
530 /*IsInput=*/false);
531
532 if (FResult.isPoison())
533 return FResult;
534
535 APFloat Result = FResult.asFloat();
536 return applyNaNPropagation(Result, Inputs: {&FLHS, &FRHS});
537 });
538 }
539
540 AnyValue
541 computeTriOp(Type *Ty, const AnyValue &Op1, const AnyValue &Op2,
542 const AnyValue &Op3,
543 function_ref<AnyValue(const AnyValue &, const AnyValue &,
544 const AnyValue &)>
545 ScalarFn) {
546 if (Ty->isVectorTy()) {
547 auto &Op1Vec = Op1.asAggregate();
548 auto &Op2Vec = Op2.asAggregate();
549 auto &Op3Vec = Op3.asAggregate();
550 std::vector<AnyValue> ResVec;
551 ResVec.reserve(n: Op1Vec.size());
552 for (const auto &[ScalarOp1, ScalarOp2, ScalarOp3] :
553 zip(t: Op1Vec, u: Op2Vec, args: Op3Vec))
554 ResVec.push_back(x: ScalarFn(ScalarOp1, ScalarOp2, ScalarOp3));
555 return std::move(ResVec);
556 }
557 return ScalarFn(Op1, Op2, Op3);
558 }
559
560 void visitTriOp(Instruction &I,
561 function_ref<AnyValue(const AnyValue &, const AnyValue &,
562 const AnyValue &)>
563 ScalarFn) {
564 setResult(I, V: computeTriOp(Ty: I.getType(), Op1: getValue(V: I.getOperand(i: 0)),
565 Op2: getValue(V: I.getOperand(i: 1)),
566 Op3: getValue(V: I.getOperand(i: 2)), ScalarFn));
567 }
568
569 void visitIntTriOp(
570 Instruction &I,
571 function_ref<AnyValue(const APInt &, const APInt &, const APInt &)>
572 ScalarFn) {
573 visitTriOp(I,
574 ScalarFn: [&](const AnyValue &Op1, const AnyValue &Op2,
575 const AnyValue &Op3) -> AnyValue {
576 if (Op1.isPoison() || Op2.isPoison() || Op3.isPoison())
577 return AnyValue::poison();
578 return ScalarFn(Op1.asInteger(), Op2.asInteger(),
579 Op3.asInteger());
580 });
581 }
582
583 AnyValue visitIntTriOpWithResult(
584 Type *RetTy, const AnyValue &Op1, const AnyValue &Op2,
585 const AnyValue &Op3,
586 function_ref<AnyValue(const APInt &, const APInt &, const APInt &)>
587 ScalarFn) {
588 return computeTriOp(
589 Ty: RetTy, Op1, Op2, Op3,
590 ScalarFn: [&](const AnyValue &Op1Inner, const AnyValue &Op2Inner,
591 const AnyValue &Op3Inner) -> AnyValue {
592 if (Op1Inner.isPoison() || Op2Inner.isPoison() || Op3Inner.isPoison())
593 return AnyValue::poison();
594 return ScalarFn(Op1Inner.asInteger(), Op2Inner.asInteger(),
595 Op3Inner.asInteger());
596 });
597 }
598
599 AnyValue visitFPTriOpWithResult(
600 Type *RetTy, const FastMathFlags &FMF, const AnyValue &Op1,
601 const AnyValue &Op2, const AnyValue &Op3,
602 function_ref<APFloat(const APFloat &, const APFloat &, const APFloat &)>
603 ScalarFn) {
604 DenormalMode DenormMode = getCurrentDenormalMode(Ty: RetTy);
605
606 if (!Ctx.isDefaultFPEnv())
607 reportImmediateUB() << "Non-constrained floating-point operation assumes "
608 "default floating-point environment";
609
610 return computeTriOp(
611 Ty: RetTy, Op1, Op2, Op3,
612 ScalarFn: [&](const AnyValue &Op1Inner, const AnyValue &Op2Inner,
613 const AnyValue &Op3Inner) -> AnyValue {
614 if (Op1Inner.isPoison() || Op2Inner.isPoison() || Op3Inner.isPoison())
615 return AnyValue::poison();
616
617 AnyValue ValidatedOp1 =
618 handleFMFFlags(Val: Op1Inner, FMF, /*IsInput=*/true);
619 AnyValue ValidatedOp2 =
620 handleFMFFlags(Val: Op2Inner, FMF, /*IsInput=*/true);
621 AnyValue ValidatedOp3 =
622 handleFMFFlags(Val: Op3Inner, FMF, /*IsInput=*/true);
623 if (ValidatedOp1.isPoison())
624 return ValidatedOp1;
625 if (ValidatedOp2.isPoison())
626 return ValidatedOp2;
627 if (ValidatedOp3.isPoison())
628 return ValidatedOp3;
629
630 // Flush input denormals
631 APFloat FOp1 = handleDenormal(Val: ValidatedOp1.asFloat(),
632 Mode: DenormMode.Input, /*IsInput=*/true);
633 APFloat FOp2 = handleDenormal(Val: ValidatedOp2.asFloat(),
634 Mode: DenormMode.Input, /*IsInput=*/true);
635 APFloat FOp3 = handleDenormal(Val: ValidatedOp3.asFloat(),
636 Mode: DenormMode.Input, /*IsInput=*/true);
637
638 APFloat RawResult = ScalarFn(FOp1, FOp2, FOp3);
639
640 // Flush output denormals and handle fast-math flags.
641 AnyValue FResult = handleFMFFlags(
642 Val: handleDenormal(Val: RawResult, Mode: DenormMode.Output, /*IsInput=*/false),
643 FMF,
644 /*IsInput=*/false);
645
646 if (FResult.isPoison())
647 return FResult;
648
649 APFloat Result = FResult.asFloat();
650 return applyNaNPropagation(Result, Inputs: {&FOp1, &FOp2, &FOp3});
651 });
652 }
653
654 void jumpTo(Instruction &Terminator, BasicBlock *DestBB) {
655 if (!Handler.onBBJump(I&: Terminator, To&: *DestBB)) {
656 setFailed();
657 return;
658 }
659 BasicBlock *From = CurrentFrame->BB;
660 CurrentFrame->BB = DestBB;
661 CurrentFrame->PC = DestBB->begin();
662 // Update PHI nodes in batch to avoid the interference between PHI nodes.
663 // We need to store the incoming values into a temporary buffer.
664 // Otherwise, the incoming value may be overwritten before it is
665 // used by other PHI nodes.
666 SmallVector<std::pair<PHINode *, AnyValue>> IncomingValues;
667 PHINode *PHI = nullptr;
668 while ((PHI = dyn_cast<PHINode>(Val&: CurrentFrame->PC))) {
669 AnyValue IncomingVal = getValue(V: PHI->getIncomingValueForBlock(BB: From));
670
671 // Fast-math flags validation
672 if (isa<FPMathOperator>(Val: PHI)) {
673 FastMathFlags FMF = PHI->getFastMathFlags();
674 if (FMF.any())
675 IncomingVal =
676 handleFMFFlags(Val: std::move(IncomingVal), FMF, /*IsInput=*/true);
677 }
678
679 IncomingValues.emplace_back(Args&: PHI, Args&: IncomingVal);
680 ++CurrentFrame->PC;
681 }
682 for (auto &[K, V] : IncomingValues)
683 setResult(I&: *K, V: std::move(V));
684 }
685
686 /// Helper function to determine whether an inline asm is a no-op, which is
687 /// used to implement black_box style optimization blockers.
688 bool isNoopInlineAsm(Value *V, Type *RetTy) {
689 if (auto *Asm = dyn_cast<InlineAsm>(Val: V))
690 return Asm->getAsmString().empty() && RetTy->isVoidTy();
691 return false;
692 }
693
694 DenormalMode getCurrentDenormalMode(Type *Ty) {
695 return CurrentFrame->Func.getDenormalMode(
696 FPType: Ty->getScalarType()->getFltSemantics());
697 }
698
699 // Helper function to convert BooleanKind to bool. Report an immediate UB if
700 // a poison is found.
701 bool getBooleanNonPoison(BooleanKind Boolean) {
702 if (Boolean == BooleanKind::Poison)
703 reportImmediateUB() << "Unexpected poison boolean value";
704 return Boolean == BooleanKind::True;
705 }
706
707 APInt getIntNonPoison(const AnyValue &V) {
708 if (V.isPoison()) {
709 reportImmediateUB() << "Unexpected poison integer value.";
710 return APInt::getZero(numBits: 64);
711 }
712 return V.asInteger();
713 }
714
715 AnyValue callMemTransferIntrinsic(CallBase &CB, ArrayRef<AnyValue> Args,
716 Intrinsic::ID IID) {
717 const AnyValue &Dest = Args[0];
718 const AnyValue &Src = Args[1];
719 const AnyValue &Length = Args[2];
720 // TODO: Handle isvolatile argument.
721 if (Length.isPoison()) {
722 reportImmediateUB() << "Memory transfer intrinsic with poison length.";
723 return AnyValue();
724 }
725
726 const APInt &LengthInt = Args[2].asInteger();
727 if (LengthInt.getActiveBits() > 64) {
728 reportImmediateUB()
729 << "Memory transfer intrinsic length overflows uint64_t.";
730 return AnyValue();
731 }
732
733 const uint64_t Len = LengthInt.getZExtValue();
734 if (Len == 0)
735 return AnyValue();
736
737 if (Dest.isPoison()) {
738 reportImmediateUB()
739 << "Memory transfer intrinsic with poison destination pointer.";
740 return AnyValue();
741 }
742
743 if (Src.isPoison()) {
744 reportImmediateUB()
745 << "Memory transfer intrinsic with poison source pointer.";
746 return AnyValue();
747 }
748
749 const Pointer &DstPtr = Dest.asPointer();
750 const Pointer &SrcPtr = Src.asPointer();
751
752 Align DstAlign = CB.getParamAlign(ArgNo: 0).valueOrOne();
753 Align SrcAlign = CB.getParamAlign(ArgNo: 1).valueOrOne();
754
755 auto [SrcMO, SrcOffset] =
756 verifyMemAccess(Ptr: SrcPtr, AccessSize: Len, Alignment: SrcAlign, /*IsStore=*/false);
757 if (!SrcMO)
758 return AnyValue();
759
760 auto [DstMO, DstOffset] =
761 verifyMemAccess(Ptr: DstPtr, AccessSize: Len, Alignment: DstAlign, /*IsStore=*/true);
762 if (!DstMO)
763 return AnyValue();
764
765 if (IID == Intrinsic::memcpy || IID == Intrinsic::memcpy_inline) {
766 if (SrcMO == DstMO && SrcOffset != DstOffset) {
767 const uint64_t SrcEnd = SrcOffset + Len;
768 const uint64_t DstEnd = DstOffset + Len;
769 if (SrcOffset < DstEnd && DstOffset < SrcEnd) {
770 reportImmediateUB()
771 << "memcpy with overlapping source and destination.";
772 return AnyValue();
773 }
774 }
775 }
776
777 MutableArrayRef<Byte> DstBytes = DstMO->getBytes().slice(N: DstOffset, M: Len);
778 ArrayRef<Byte> SrcBytes = SrcMO->getBytes().slice(N: SrcOffset, M: Len);
779 std::memmove(dest: DstBytes.data(), src: SrcBytes.data(), n: Len * sizeof(Byte));
780 return AnyValue();
781 }
782
783 AnyValue callMemSetIntrinsic(CallBase &CB, ArrayRef<AnyValue> Args) {
784 const AnyValue &Dest = Args[0];
785 const AnyValue &Val = Args[1];
786 const AnyValue &Length = Args[2];
787
788 if (Length.isPoison()) {
789 reportImmediateUB() << "memset called with poison length.";
790 return AnyValue();
791 }
792
793 const APInt &LengthInt = Length.asInteger();
794 if (LengthInt.getActiveBits() > 64) {
795 reportImmediateUB() << "memset called with length overflows uint64_t.";
796 return AnyValue();
797 }
798
799 const uint64_t Len = LengthInt.getZExtValue();
800 if (Len == 0)
801 return AnyValue();
802
803 if (Dest.isPoison()) {
804 reportImmediateUB() << "memset called with poison destination pointer.";
805 return AnyValue();
806 }
807
808 const Pointer &DstPtr = Dest.asPointer();
809
810 Align DstAlign = CB.getParamAlign(ArgNo: 0).valueOrOne();
811 auto [DstMO, DstOffset] =
812 verifyMemAccess(Ptr: DstPtr, AccessSize: Len, Alignment: DstAlign, /*IsStore=*/true);
813 if (!DstMO)
814 return AnyValue();
815
816 Byte FillByte = Val.isPoison()
817 ? Byte::poison()
818 : Byte::concrete(Val: Val.asInteger().getZExtValue());
819 fill(Range: DstMO->getBytes().slice(N: DstOffset, M: Len), Value&: FillByte);
820 return AnyValue();
821 }
822
823 static BooleanKind getMaskLane(const AnyValue &Mask, size_t I) {
824 return Mask.asAggregate()[I].asBoolean();
825 }
826
827 AnyValue callExperimentalVectorHistogramIntrinsic(CallBase &CB,
828 ArrayRef<AnyValue> Args,
829 Intrinsic::ID IID) {
830 struct LaneUpdate {
831 MemoryObject *MO;
832 uint64_t Offset;
833 uint64_t Count;
834 AnyValue Old;
835 AnyValue New;
836 };
837
838 const auto &Ptrs = Args[0].asAggregate();
839 const AnyValue &Update = Args[1];
840 const AnyValue &Mask = Args[2];
841 Type *ElemTy = CB.getArgOperand(i: 1)->getType();
842 const uint64_t AccessSize = Ctx.getEffectiveTypeStoreSize(Ty: ElemTy);
843
844 SmallVector<LaneUpdate, 8> Lanes;
845 Lanes.reserve(N: Ptrs.size());
846 for (size_t I = 0, E = Ptrs.size(); I != E; ++I) {
847 switch (getMaskLane(Mask, I)) {
848 case BooleanKind::False:
849 continue;
850 case BooleanKind::Poison:
851 reportImmediateUB()
852 << "Poison mask lane in experimental vector histogram intrinsic.";
853 return AnyValue();
854 case BooleanKind::True:
855 break;
856 }
857
858 if (Ptrs[I].isPoison()) {
859 reportImmediateUB() << "Poison pointer lane in experimental vector "
860 "histogram intrinsic.";
861 return AnyValue();
862 }
863
864 auto [MO, Offset] =
865 verifyMemAccess(Ptr: Ptrs[I].asPointer(), AccessSize, Alignment: Align(1),
866 /*IsStore=*/true);
867 if (!MO)
868 return AnyValue();
869
870 Lanes.push_back(Elt: {.MO: MO, .Offset: Offset, .Count: 0, .Old: AnyValue(), .New: AnyValue()});
871 }
872
873 for (LaneUpdate &Lane : Lanes) {
874 Lane.Count = count_if(Range&: Lanes, P: [&](const LaneUpdate &Other) {
875 return Other.MO == Lane.MO && Other.Offset == Lane.Offset;
876 });
877 Lane.Old = Ctx.load(MO&: *Lane.MO, Offset: Lane.Offset, ValTy: ElemTy);
878 }
879
880 for (LaneUpdate &Lane : Lanes) {
881 const AnyValue &Old = Lane.Old;
882 AnyValue &New = Lane.New;
883
884 if (Old.isPoison() || Update.isPoison()) {
885 New = AnyValue::poison();
886 } else {
887 const APInt &OldInt = Old.asInteger();
888 const APInt &UpdateInt = Update.asInteger();
889
890 switch (IID) {
891 case Intrinsic::experimental_vector_histogram_add:
892 New = OldInt + UpdateInt * APInt(UpdateInt.getBitWidth(), Lane.Count,
893 /*isSigned=*/false,
894 /*implicitTrunc=*/true);
895 break;
896 case Intrinsic::experimental_vector_histogram_uadd_sat: {
897 APInt Acc = OldInt;
898 for (uint64_t I = 0; I != Lane.Count; ++I)
899 Acc = Acc.uadd_sat(RHS: UpdateInt);
900 New = Acc;
901 break;
902 }
903 case Intrinsic::experimental_vector_histogram_umax:
904 New = APIntOps::umax(A: OldInt, B: UpdateInt);
905 break;
906 case Intrinsic::experimental_vector_histogram_umin:
907 New = APIntOps::umin(A: OldInt, B: UpdateInt);
908 break;
909 default:
910 llvm_unreachable("Unexpected histogram intrinsic ID");
911 }
912 }
913 }
914
915 for (const LaneUpdate &Lane : Lanes)
916 Ctx.store(MO&: *Lane.MO, Offset: Lane.Offset, Val: Lane.New, ValTy: ElemTy);
917
918 return AnyValue();
919 }
920
921public:
922 InstExecutor(Context &C, EventHandler &H, Function &F,
923 ArrayRef<AnyValue> Args, AnyValue &RetVal)
924 : ExecutorBase(C, H), DL(Ctx.getDataLayout()),
925 Lib(Ctx, Handler, DL, static_cast<ExecutorBase &>(*this)) {
926 CallStack.emplace_back(args&: F, /*CallSite=*/args: nullptr, /*LastFrame=*/args: nullptr, args&: Args,
927 args&: RetVal, args: Ctx.getTLIImpl());
928 }
929
930 void visitReturnInst(ReturnInst &RI) {
931 if (auto *RV = RI.getReturnValue())
932 CurrentFrame->RetVal = getValue(V: RV);
933 else
934 CurrentFrame->RetVal = AnyValue();
935 CurrentFrame->State = FrameState::Exit;
936 if (!Handler.onInstructionExecuted(I&: RI, Result: None))
937 setFailed();
938 }
939
940 void visitUncondBrInst(UncondBrInst &BI) { jumpTo(Terminator&: BI, DestBB: BI.getSuccessor()); }
941
942 void visitCondBrInst(CondBrInst &BI) {
943 switch (getValue(V: BI.getCondition()).asBoolean()) {
944 case BooleanKind::True:
945 jumpTo(Terminator&: BI, DestBB: BI.getSuccessor(i: 0));
946 return;
947 case BooleanKind::False:
948 jumpTo(Terminator&: BI, DestBB: BI.getSuccessor(i: 1));
949 return;
950 case BooleanKind::Poison:
951 reportImmediateUB() << "Branch on poison condition.";
952 return;
953 }
954 }
955
956 void visitSwitchInst(SwitchInst &SI) {
957 auto &Cond = getValue(V: SI.getCondition());
958 if (Cond.isPoison()) {
959 reportImmediateUB() << "Switch on poison condition.";
960 return;
961 }
962 for (auto &Case : SI.cases()) {
963 if (Case.getCaseValue()->getValue() == Cond.asInteger()) {
964 jumpTo(Terminator&: SI, DestBB: Case.getCaseSuccessor());
965 return;
966 }
967 }
968 jumpTo(Terminator&: SI, DestBB: SI.getDefaultDest());
969 }
970
971 void visitUnreachableInst(UnreachableInst &) {
972 reportImmediateUB() << "Unreachable code.";
973 }
974
975 void visitCallBrInst(CallBrInst &CI) {
976 if (isNoopInlineAsm(V: CI.getCalledOperand(), RetTy: CI.getType())) {
977 jumpTo(Terminator&: CI, DestBB: CI.getDefaultDest());
978 return;
979 }
980
981 Handler.onUnrecognizedInstruction(I&: CI);
982 setFailed();
983 }
984
985 void visitIndirectBrInst(IndirectBrInst &IBI) {
986 auto &Target = getValue(V: IBI.getAddress());
987 if (Target.isPoison()) {
988 reportImmediateUB() << "Indirect branch on poison.";
989 return;
990 }
991 if (BasicBlock *DestBB = Ctx.getTargetBlock(Ptr: Target.asPointer())) {
992 if (any_of(Range: IBI.successors(),
993 P: [DestBB](BasicBlock *Succ) { return Succ == DestBB; }))
994 jumpTo(Terminator&: IBI, DestBB);
995 else
996 reportImmediateUB() << "Indirect branch on unlisted target BB.";
997
998 return;
999 }
1000 reportImmediateUB() << "Indirect branch on invalid target BB.";
1001 }
1002
1003 void returnFromCallee() {
1004 auto &CB = cast<CallBase>(Val&: *CurrentFrame->PC);
1005 CurrentFrame->CalleeArgs.clear();
1006 AnyValue &RetVal = CurrentFrame->CalleeRetVal;
1007 if (Type *RetTy = CB.getType(); !RetTy->isVoidTy()) {
1008 // Handle attributes on the return value (Attributes from resolved callee
1009 // should be applied if available).
1010 AttributeSet AttrsAtCallSite = CB.getRetAttributes();
1011 AttributeSet AttrsAtCallee =
1012 CurrentFrame->ResolvedCallee->getAttributes().getRetAttrs();
1013 handleAttributes(Ty: RetTy, V&: RetVal, AttrsAtCallSite, AttrsAtCallee);
1014 handleMetadata(Ty: RetTy, V&: RetVal, I&: CB);
1015 }
1016 setResult(I&: CB, V: std::move(RetVal));
1017
1018 for (auto &ByValArg : CurrentFrame->CalleeByValArgs)
1019 Ctx.free(Obj: *ByValArg);
1020 CurrentFrame->CalleeByValArgs.clear();
1021
1022 if (auto *II = dyn_cast<InvokeInst>(Val: &CB))
1023 jumpTo(Terminator&: *II, DestBB: II->getNormalDest());
1024 else if (CurrentFrame->State == FrameState::Pending)
1025 ++CurrentFrame->PC;
1026 }
1027
1028 AnyValue callIntrinsic(CallBase &CB, ArrayRef<AnyValue> Args) {
1029 Intrinsic::ID IID = CB.getIntrinsicID();
1030 Type *RetTy = CB.getType();
1031 const FastMathFlags FMF = CB.getFastMathFlagsOrNone();
1032
1033 switch (IID) {
1034 case Intrinsic::assume:
1035 switch (Args[0].asBoolean()) {
1036 case BooleanKind::True:
1037 for (unsigned Idx = 0; Idx < CB.getNumOperandBundles(); Idx++) {
1038 OperandBundleUse OBU = CB.getOperandBundleAt(Index: Idx);
1039 auto GetBundleArg = [&](uint32_t Offset) -> Value * {
1040 return OBU.Inputs[Offset];
1041 };
1042 if (OBU.Inputs.empty())
1043 continue;
1044 Value *WasOnVal = GetBundleArg(0);
1045 // Bail out on unrecognized operand bundles.
1046 if (!WasOnVal->getType()->isPointerTy())
1047 continue;
1048 unsigned AS = WasOnVal->getType()->getPointerAddressSpace();
1049 const AnyValue &WasOn = getValue(V: WasOnVal);
1050 if (WasOn.isPoison()) {
1051 reportImmediateUB() << "Assume on poison pointer.";
1052 break;
1053 }
1054 const Pointer &WasOnPtr = WasOn.asPointer();
1055 Attribute::AttrKind Kind =
1056 Attribute::getAttrKindFromName(AttrName: OBU.getTagName());
1057 switch (Kind) {
1058 case Attribute::Alignment: {
1059 // Alignment assumptions should have 2 or 3 arguments.
1060 APInt Alignment = getIntNonPoison(V: getValue(V: GetBundleArg(1)));
1061 APInt CheckedAddr = WasOnPtr.address();
1062 if (OBU.Inputs.size() == 3) {
1063 APInt Offset = getIntNonPoison(V: getValue(V: GetBundleArg(2)));
1064 CheckedAddr -= Offset.sextOrTrunc(width: CheckedAddr.getBitWidth());
1065 }
1066 if (!Alignment.isPowerOf2()) {
1067 if (!CheckedAddr.isZero())
1068 reportImmediateUB() << "Assume on pointer " << WasOn
1069 << " with a nonzero adjusted address and a "
1070 "non-power-of-two alignment "
1071 << Alignment << '.';
1072 break;
1073 }
1074 if (CheckedAddr.countr_zero() < Alignment.logBase2())
1075 reportImmediateUB()
1076 << "The pointer " << WasOn << " violates align(" << Alignment
1077 << ") assumption.";
1078 break;
1079 }
1080 case Attribute::NonNull:
1081 if (WasOnPtr.isNullPtr(AS, DL))
1082 reportImmediateUB()
1083 << "The pointer " << WasOn << " violates nonnull assumption.";
1084 break;
1085 case Attribute::Dereferenceable:
1086 case Attribute::DereferenceableOrNull: {
1087 APInt DereferenceableBytes =
1088 getIntNonPoison(V: getValue(V: GetBundleArg(1)));
1089 // Only n > 0 implies that the pointer is dereferenceable.
1090 if (DereferenceableBytes.isZero())
1091 break;
1092 if (violatesDereferenceableBytesAttr(
1093 V: WasOn, Bytes: DereferenceableBytes.getLimitedValue(),
1094 OrNull: Kind == Attribute::DereferenceableOrNull, AS, Ctx))
1095 reportImmediateUB() << "The pointer " << WasOn << " violates "
1096 << (Kind == Attribute::DereferenceableOrNull
1097 ? "dereferenceable_or_null("
1098 : "dereferenceable(")
1099 << DereferenceableBytes << ") assumption.";
1100 break;
1101 }
1102 default:
1103 // TODO: handle other operand bundles like separate_storage.
1104 break;
1105 }
1106 }
1107 break;
1108 case BooleanKind::False:
1109 case BooleanKind::Poison:
1110 reportImmediateUB() << "Assume on false or poison condition.";
1111 break;
1112 }
1113 return AnyValue();
1114 case Intrinsic::lifetime_start:
1115 case Intrinsic::lifetime_end: {
1116 auto Ptr = Args[0];
1117 if (Ptr.isPoison())
1118 return AnyValue();
1119 auto *MO = Ctx.checkProvenance(Ptr: Ptr.asPointer(),
1120 Check: [](const Provenance &) { return true; });
1121 assert(MO && "Memory object accessed by lifetime intrinsic should be "
1122 "always valid.");
1123 if (IID == Intrinsic::lifetime_start) {
1124 MO->setState(MemoryObjectState::Alive);
1125 fill(Range: MO->getBytes(), Value: Byte::undef());
1126 } else {
1127 fill(Range: MO->getBytes(), Value: Byte::poison());
1128 MO->setState(MemoryObjectState::Dead);
1129 }
1130 return AnyValue();
1131 }
1132 case Intrinsic::ssa_copy:
1133 case Intrinsic::expect:
1134 case Intrinsic::expect_with_probability:
1135 return Args[0];
1136 case Intrinsic::donothing:
1137 return AnyValue();
1138 case Intrinsic::vscale: {
1139 const unsigned BitWidth = RetTy->getScalarSizeInBits();
1140 const APInt VScale(64, Ctx.getVScale());
1141 if (!VScale.isIntN(N: BitWidth))
1142 return AnyValue::poison();
1143 return VScale.zextOrTrunc(width: BitWidth);
1144 }
1145 case Intrinsic::abs: {
1146 const bool IsIntMinPoison = getBooleanNonPoison(Boolean: Args[1].asBoolean());
1147 return visitIntUnOpWithResult(
1148 RetTy, Operand: Args[0], ScalarFn: [&](const APInt &Operand) -> AnyValue {
1149 if (IsIntMinPoison && Operand.isMinSignedValue())
1150 return AnyValue::poison();
1151 return Operand.abs();
1152 });
1153 }
1154 case Intrinsic::smax: {
1155 return visitIntBinOpWithResult(
1156 RetTy, LHS: Args[0], RHS: Args[1],
1157 ScalarFn: [](const APInt &LHS, const APInt &RHS) -> AnyValue {
1158 return APIntOps::smax(A: LHS, B: RHS);
1159 });
1160 }
1161 case Intrinsic::smin: {
1162 return visitIntBinOpWithResult(
1163 RetTy, LHS: Args[0], RHS: Args[1],
1164 ScalarFn: [](const APInt &LHS, const APInt &RHS) -> AnyValue {
1165 return APIntOps::smin(A: LHS, B: RHS);
1166 });
1167 }
1168 case Intrinsic::umax: {
1169 return visitIntBinOpWithResult(
1170 RetTy, LHS: Args[0], RHS: Args[1],
1171 ScalarFn: [](const APInt &LHS, const APInt &RHS) -> AnyValue {
1172 return APIntOps::umax(A: LHS, B: RHS);
1173 });
1174 }
1175 case Intrinsic::umin: {
1176 return visitIntBinOpWithResult(
1177 RetTy, LHS: Args[0], RHS: Args[1],
1178 ScalarFn: [](const APInt &LHS, const APInt &RHS) -> AnyValue {
1179 return APIntOps::umin(A: LHS, B: RHS);
1180 });
1181 }
1182 case Intrinsic::scmp:
1183 case Intrinsic::ucmp: {
1184 const unsigned BitWidth = RetTy->getScalarSizeInBits();
1185 return visitIntBinOpWithResult(
1186 RetTy, LHS: Args[0], RHS: Args[1],
1187 ScalarFn: [&](const APInt &LHS, const APInt &RHS) -> AnyValue {
1188 if (LHS == RHS)
1189 return APInt::getZero(numBits: BitWidth);
1190 if (IID == Intrinsic::scmp)
1191 return LHS.slt(RHS) ? APInt::getAllOnes(numBits: BitWidth)
1192 : APInt(BitWidth, 1);
1193 return LHS.ult(RHS) ? APInt::getAllOnes(numBits: BitWidth)
1194 : APInt(BitWidth, 1);
1195 });
1196 }
1197 case Intrinsic::bitreverse: {
1198 return visitIntUnOpWithResult(RetTy, Operand: Args[0],
1199 ScalarFn: [](const APInt &Operand) -> AnyValue {
1200 return Operand.reverseBits();
1201 });
1202 }
1203 case Intrinsic::bswap: {
1204 return visitIntUnOpWithResult(
1205 RetTy, Operand: Args[0],
1206 ScalarFn: [](const APInt &Operand) -> AnyValue { return Operand.byteSwap(); });
1207 }
1208 case Intrinsic::ctpop: {
1209 return visitIntUnOpWithResult(
1210 RetTy, Operand: Args[0], ScalarFn: [](const APInt &Operand) -> AnyValue {
1211 return APInt(Operand.getBitWidth(), Operand.popcount());
1212 });
1213 }
1214 case Intrinsic::ctlz:
1215 case Intrinsic::cttz: {
1216 const bool IsZeroPoison = getBooleanNonPoison(Boolean: Args[1].asBoolean());
1217 return visitIntUnOpWithResult(
1218 RetTy, Operand: Args[0], ScalarFn: [&](const APInt &Operand) -> AnyValue {
1219 if (IsZeroPoison && Operand.isZero())
1220 return AnyValue::poison();
1221 if (IID == Intrinsic::ctlz)
1222 return APInt(Operand.getBitWidth(), Operand.countl_zero());
1223 return APInt(Operand.getBitWidth(), Operand.countr_zero());
1224 });
1225 }
1226 case Intrinsic::fshl:
1227 case Intrinsic::fshr: {
1228 return visitIntTriOpWithResult(
1229 RetTy, Op1: Args[0], Op2: Args[1], Op3: Args[2],
1230 ScalarFn: [IID](const APInt &Op1, const APInt &Op2,
1231 const APInt &Op3) -> AnyValue {
1232 const unsigned BitWidth = Op1.getBitWidth();
1233 const uint64_t ShiftAmount = Op3.urem(RHS: BitWidth);
1234 const bool IsFShr = IID == Intrinsic::fshr;
1235 if (ShiftAmount == 0)
1236 return IsFShr ? Op2 : Op1;
1237 const uint64_t LShrAmount =
1238 IsFShr ? ShiftAmount : BitWidth - ShiftAmount;
1239 const uint64_t ShlAmount =
1240 !IsFShr ? ShiftAmount : BitWidth - ShiftAmount;
1241 return Op1.shl(shiftAmt: ShlAmount) | Op2.lshr(shiftAmt: LShrAmount);
1242 });
1243 }
1244 case Intrinsic::clmul: {
1245 return visitIntBinOpWithResult(
1246 RetTy, LHS: Args[0], RHS: Args[1],
1247 ScalarFn: [](const APInt &LHS, const APInt &RHS) -> AnyValue {
1248 return APIntOps::clmul(LHS, RHS);
1249 });
1250 }
1251 case Intrinsic::sadd_with_overflow:
1252 case Intrinsic::uadd_with_overflow:
1253 case Intrinsic::ssub_with_overflow:
1254 case Intrinsic::usub_with_overflow:
1255 case Intrinsic::smul_with_overflow:
1256 case Intrinsic::umul_with_overflow: {
1257 return visitOverflowIntBinOpWithResult(
1258 RetTy, LHS: Args[0], RHS: Args[1],
1259 ScalarFn: [IID](const APInt &LHS, const APInt &RHS) -> std::pair<APInt, bool> {
1260 APInt Res;
1261 bool Overflow = false;
1262 switch (IID) {
1263 case Intrinsic::sadd_with_overflow:
1264 Res = LHS.sadd_ov(RHS, Overflow);
1265 break;
1266 case Intrinsic::uadd_with_overflow:
1267 Res = LHS.uadd_ov(RHS, Overflow);
1268 break;
1269 case Intrinsic::ssub_with_overflow:
1270 Res = LHS.ssub_ov(RHS, Overflow);
1271 break;
1272 case Intrinsic::usub_with_overflow:
1273 Res = LHS.usub_ov(RHS, Overflow);
1274 break;
1275 case Intrinsic::smul_with_overflow:
1276 Res = LHS.smul_ov(RHS, Overflow);
1277 break;
1278 case Intrinsic::umul_with_overflow:
1279 Res = LHS.umul_ov(RHS, Overflow);
1280 break;
1281 default:
1282 llvm_unreachable("Unexpected intrinsic ID");
1283 }
1284 return {Res, Overflow};
1285 });
1286 }
1287 case Intrinsic::sadd_sat:
1288 case Intrinsic::uadd_sat:
1289 case Intrinsic::ssub_sat:
1290 case Intrinsic::usub_sat:
1291 case Intrinsic::sshl_sat:
1292 case Intrinsic::ushl_sat: {
1293 return visitIntBinOpWithResult(
1294 RetTy, LHS: Args[0], RHS: Args[1],
1295 ScalarFn: [IID](const APInt &LHS, const APInt &RHS) -> AnyValue {
1296 switch (IID) {
1297 case Intrinsic::sadd_sat:
1298 return LHS.sadd_sat(RHS);
1299 case Intrinsic::uadd_sat:
1300 return LHS.uadd_sat(RHS);
1301 case Intrinsic::ssub_sat:
1302 return LHS.ssub_sat(RHS);
1303 case Intrinsic::usub_sat:
1304 return LHS.usub_sat(RHS);
1305 case Intrinsic::sshl_sat: {
1306 if (RHS.uge(RHS: LHS.getBitWidth()))
1307 return AnyValue::poison();
1308 return LHS.sshl_sat(RHS);
1309 }
1310 case Intrinsic::ushl_sat: {
1311 if (RHS.uge(RHS: LHS.getBitWidth()))
1312 return AnyValue::poison();
1313 return LHS.ushl_sat(RHS);
1314 }
1315 default:
1316 llvm_unreachable("Unexpected intrinsic ID");
1317 }
1318 });
1319 }
1320 case Intrinsic::vector_reduce_add:
1321 case Intrinsic::vector_reduce_mul:
1322 case Intrinsic::vector_reduce_and:
1323 case Intrinsic::vector_reduce_or:
1324 case Intrinsic::vector_reduce_xor:
1325 case Intrinsic::vector_reduce_smax:
1326 case Intrinsic::vector_reduce_smin:
1327 case Intrinsic::vector_reduce_umax:
1328 case Intrinsic::vector_reduce_umin: {
1329 std::optional<APInt> Res;
1330 for (const auto &V : Args[0].asAggregate()) {
1331 if (V.isPoison()) {
1332 Res.reset();
1333 break;
1334 }
1335 const auto &IntV = V.asInteger();
1336 if (!Res) {
1337 Res = IntV;
1338 continue;
1339 }
1340 switch (IID) {
1341 case Intrinsic::vector_reduce_add:
1342 *Res += IntV;
1343 break;
1344 case Intrinsic::vector_reduce_mul:
1345 *Res *= IntV;
1346 break;
1347 case Intrinsic::vector_reduce_and:
1348 *Res &= IntV;
1349 break;
1350 case Intrinsic::vector_reduce_or:
1351 *Res |= IntV;
1352 break;
1353 case Intrinsic::vector_reduce_xor:
1354 *Res ^= IntV;
1355 break;
1356 case Intrinsic::vector_reduce_smax:
1357 *Res = APIntOps::smax(A: *Res, B: IntV);
1358 break;
1359 case Intrinsic::vector_reduce_smin:
1360 *Res = APIntOps::smin(A: *Res, B: IntV);
1361 break;
1362 case Intrinsic::vector_reduce_umax:
1363 *Res = APIntOps::umax(A: *Res, B: IntV);
1364 break;
1365 case Intrinsic::vector_reduce_umin:
1366 *Res = APIntOps::umin(A: *Res, B: IntV);
1367 break;
1368 default:
1369 llvm_unreachable("Unexpected intrinsic ID");
1370 }
1371 }
1372 return Res ? *Res : AnyValue::poison();
1373 }
1374 case Intrinsic::vector_insert: {
1375 assert(!Args[2].isPoison() &&
1376 "Verifier should reject poison vector_insert immarg.");
1377 const auto &Vec = Args[0].asAggregate();
1378 const auto &SubVec = Args[1].asAggregate();
1379 const auto &Idx = Args[2].asInteger();
1380 auto EC =
1381 cast<VectorType>(Val: CB.getArgOperand(i: 1)->getType())->getElementCount();
1382 const uint64_t RawOffset = Idx.getZExtValue();
1383 const uint32_t MinSize = EC.getKnownMinValue();
1384 assert(RawOffset % MinSize == 0 &&
1385 "Verifier should reject misaligned vector_insert index.");
1386 const uint64_t Chunk = RawOffset / MinSize;
1387 const uint64_t EVL = Ctx.getEVL(EC);
1388 if (Chunk > std::numeric_limits<uint64_t>::max() / EVL)
1389 return AnyValue::getPoisonValue(Ctx, Ty: RetTy);
1390 const uint64_t Offset = Chunk * EVL;
1391 if (Offset > Vec.size() || SubVec.size() > Vec.size() - Offset)
1392 return AnyValue::getPoisonValue(Ctx, Ty: RetTy);
1393 std::vector<AnyValue> Res;
1394 Res.reserve(n: Vec.size());
1395 for (size_t I = 0; I != Vec.size(); ++I) {
1396 if (I >= Offset && I < Offset + SubVec.size())
1397 Res.push_back(x: SubVec[I - Offset]);
1398 else
1399 Res.push_back(x: Vec[I]);
1400 }
1401 return std::move(Res);
1402 }
1403 case Intrinsic::vector_extract: {
1404 assert(!Args[1].isPoison() &&
1405 "Verifier should reject poison vector_extract immarg.");
1406 const auto &Vec = Args[0].asAggregate();
1407 const auto &Idx = Args[1].asInteger();
1408 auto EC = cast<VectorType>(Val: RetTy)->getElementCount();
1409 const uint64_t RawOffset = Idx.getZExtValue();
1410 const uint32_t MinSize = EC.getKnownMinValue();
1411 assert(RawOffset % MinSize == 0 &&
1412 "Verifier should reject misaligned vector_extract index.");
1413 const uint64_t Chunk = RawOffset / MinSize;
1414 const uint64_t EVL = Ctx.getEVL(EC);
1415 if (Chunk > std::numeric_limits<uint64_t>::max() / EVL)
1416 return AnyValue::getPoisonValue(Ctx, Ty: RetTy);
1417 const uint64_t Offset = Chunk * EVL;
1418 if (Offset > Vec.size() || EVL > Vec.size() - Offset)
1419 return AnyValue::getPoisonValue(Ctx, Ty: RetTy);
1420 return std::vector<AnyValue>(Vec.begin() + Offset,
1421 Vec.begin() + Offset + EVL);
1422 }
1423 case Intrinsic::vector_reverse: {
1424 auto Vec = Args[0].asAggregate();
1425 std::reverse(first: Vec.begin(), last: Vec.end());
1426 return std::move(Vec);
1427 }
1428 case Intrinsic::vector_deinterleave2:
1429 case Intrinsic::vector_deinterleave3:
1430 case Intrinsic::vector_deinterleave4:
1431 case Intrinsic::vector_deinterleave5:
1432 case Intrinsic::vector_deinterleave6:
1433 case Intrinsic::vector_deinterleave7:
1434 case Intrinsic::vector_deinterleave8: {
1435 const unsigned Factor = getDeinterleaveIntrinsicFactor(ID: IID);
1436 if (Factor == 0)
1437 llvm_unreachable("Unexpected intrinsic ID");
1438 const auto &Vec = Args[0].asAggregate();
1439 std::vector<std::vector<AnyValue>> Res(Factor);
1440 for (auto &SubVec : Res)
1441 SubVec.reserve(n: Vec.size() / Factor);
1442 for (size_t I = 0, E = Vec.size(); I != E; ++I)
1443 Res[I % Factor].push_back(x: Vec[I]);
1444
1445 std::vector<AnyValue> AggRes;
1446 AggRes.reserve(n: Factor);
1447 for (auto &SubVec : Res)
1448 AggRes.emplace_back(args: std::move(SubVec));
1449 return AnyValue(std::move(AggRes));
1450 }
1451 case Intrinsic::vector_interleave2:
1452 case Intrinsic::vector_interleave3:
1453 case Intrinsic::vector_interleave4:
1454 case Intrinsic::vector_interleave5:
1455 case Intrinsic::vector_interleave6:
1456 case Intrinsic::vector_interleave7:
1457 case Intrinsic::vector_interleave8: {
1458 const unsigned Factor = getInterleaveIntrinsicFactor(ID: IID);
1459 if (Factor == 0)
1460 llvm_unreachable("Unexpected intrinsic ID");
1461 const auto &Vec = Args[0].asAggregate();
1462 std::vector<AnyValue> Res;
1463 Res.reserve(n: Vec.size() * Factor);
1464 for (size_t I = 0, E = Vec.size(); I != E; ++I) {
1465 for (unsigned J = 0; J != Factor; ++J)
1466 Res.push_back(x: Args[J].asAggregate()[I]);
1467 }
1468 return std::move(Res);
1469 }
1470 case Intrinsic::vector_splice_left: {
1471 if (Args[2].isPoison())
1472 return AnyValue::getPoisonValue(Ctx, Ty: RetTy);
1473 const auto &LHS = Args[0].asAggregate();
1474 const auto &RHS = Args[1].asAggregate();
1475 const auto &Off = Args[2].asInteger();
1476 const size_t Len = LHS.size();
1477 if (Off.ugt(RHS: Len))
1478 return AnyValue::getPoisonValue(Ctx, Ty: RetTy);
1479 uint64_t Offset = Off.getZExtValue();
1480 std::vector<AnyValue> Res;
1481 Res.reserve(n: Len);
1482 for (size_t I = 0; I != Len; ++I) {
1483 size_t Pos = I + Offset;
1484 Res.push_back(x: Pos < Len ? LHS[Pos] : RHS[Pos - Len]);
1485 }
1486 return std::move(Res);
1487 }
1488 case Intrinsic::vector_splice_right: {
1489 if (Args[2].isPoison())
1490 return AnyValue::getPoisonValue(Ctx, Ty: RetTy);
1491 const auto &LHS = Args[0].asAggregate();
1492 const auto &RHS = Args[1].asAggregate();
1493 const auto &Off = Args[2].asInteger();
1494 const size_t Len = LHS.size();
1495 if (Off.ugt(RHS: Len))
1496 return AnyValue::getPoisonValue(Ctx, Ty: RetTy);
1497 uint64_t Offset = Len - Off.getZExtValue();
1498 std::vector<AnyValue> Res;
1499 Res.reserve(n: Len);
1500 for (size_t I = 0; I != Len; ++I) {
1501 size_t Pos = I + Offset;
1502 Res.push_back(x: Pos < Len ? LHS[Pos] : RHS[Pos - Len]);
1503 }
1504 return std::move(Res);
1505 }
1506 case Intrinsic::stepvector: {
1507 std::vector<AnyValue> Res;
1508 const uint32_t Len =
1509 Ctx.getEVL(EC: cast<VectorType>(Val: RetTy)->getElementCount());
1510 const unsigned BitWidth = RetTy->getScalarSizeInBits();
1511 Res.reserve(n: Len);
1512 for (uint64_t I = 0; I != Len; ++I) {
1513 Res.push_back(
1514 x: APInt(BitWidth, I, /*IsSigned=*/false, /*ImplicitTrunc=*/true));
1515 }
1516 return std::move(Res);
1517 }
1518 case Intrinsic::vector_reduce_fadd:
1519 case Intrinsic::vector_reduce_fmul:
1520 case Intrinsic::vector_reduce_fmaximum:
1521 case Intrinsic::vector_reduce_fminimum:
1522 case Intrinsic::vector_reduce_fmaximumnum:
1523 case Intrinsic::vector_reduce_fminimumnum: {
1524 const auto DenormMode = getCurrentDenormalMode(Ty: RetTy);
1525 const bool HasStart = IID == Intrinsic::vector_reduce_fadd ||
1526 IID == Intrinsic::vector_reduce_fmul;
1527 const AnyValue &Vector = HasStart ? Args[1] : Args[0];
1528 std::optional<APFloat> Res;
1529 if (HasStart) {
1530 if (Args[0].isPoison())
1531 return AnyValue::poison();
1532 const AnyValue ValidatedStart =
1533 handleFMFFlags(Val: Args[0], FMF, /*IsInput=*/true);
1534 if (ValidatedStart.isPoison())
1535 return AnyValue::poison();
1536 Res = handleDenormal(Val: ValidatedStart.asFloat(), Mode: DenormMode.Input,
1537 /*IsInput=*/true);
1538 }
1539 for (const auto &V : Vector.asAggregate()) {
1540 if (V.isPoison())
1541 return AnyValue::poison();
1542 const AnyValue ValidatedOp = handleFMFFlags(Val: V, FMF, /*IsInput=*/true);
1543 if (ValidatedOp.isPoison())
1544 return AnyValue::poison();
1545 APFloat Op = handleDenormal(Val: ValidatedOp.asFloat(), Mode: DenormMode.Input,
1546 /*IsInput=*/true);
1547 if (!Res) {
1548 Res = std::move(Op);
1549 continue;
1550 }
1551 switch (IID) {
1552 case Intrinsic::vector_reduce_fadd:
1553 *Res = *Res + Op;
1554 break;
1555 case Intrinsic::vector_reduce_fmul:
1556 *Res = *Res * Op;
1557 break;
1558 case Intrinsic::vector_reduce_fmaximum:
1559 *Res = maximum(A: *Res, B: Op);
1560 break;
1561 case Intrinsic::vector_reduce_fminimum:
1562 *Res = minimum(A: *Res, B: Op);
1563 break;
1564 case Intrinsic::vector_reduce_fmaximumnum:
1565 *Res = maximumnum(A: *Res, B: Op);
1566 break;
1567 case Intrinsic::vector_reduce_fminimumnum:
1568 *Res = minimumnum(A: *Res, B: Op);
1569 break;
1570 default:
1571 llvm_unreachable("Unexpected intrinsic ID");
1572 }
1573 }
1574 assert(Res.has_value());
1575 const AnyValue ValidatedRes =
1576 handleFMFFlags(Val: *Res, FMF, /*IsInput=*/false);
1577 if (ValidatedRes.isPoison())
1578 return AnyValue::poison();
1579 const APFloat FRes =
1580 handleDenormal(Val: ValidatedRes.asFloat(), Mode: DenormMode.Output,
1581 /*IsInput=*/false);
1582 SmallVector<const APFloat *, 8> InputVec;
1583 InputVec.reserve(N: Vector.asAggregate().size());
1584 transform(
1585 Range: Vector.asAggregate(), d_first: std::back_inserter(x&: InputVec),
1586 F: [](const AnyValue &V) -> const APFloat * { return &V.asFloat(); });
1587 return applyNaNPropagation(Result: FRes, Inputs: InputVec);
1588 }
1589 case Intrinsic::vector_reduce_fmax:
1590 case Intrinsic::vector_reduce_fmin: {
1591 const auto DenormMode = getCurrentDenormalMode(Ty: RetTy);
1592 const auto &Vector = Args[0].asAggregate();
1593 SmallVector<APFloat, 8> InputFloats;
1594 SmallVector<const APFloat *, 8> InputVec;
1595 InputFloats.reserve(N: Vector.size());
1596 InputVec.reserve(N: Vector.size());
1597 for (const auto &V : Vector) {
1598 if (V.isPoison())
1599 return AnyValue::poison();
1600 const AnyValue ValidatedOp = handleFMFFlags(Val: V, FMF, /*IsInput=*/true);
1601 if (ValidatedOp.isPoison())
1602 return AnyValue::poison();
1603 InputFloats.push_back(Elt: handleDenormal(Val: ValidatedOp.asFloat(),
1604 Mode: DenormMode.Input,
1605 /*IsInput=*/true));
1606 InputVec.push_back(Elt: &InputFloats.back());
1607 }
1608 assert(!InputVec.empty());
1609 SmallVector<APFloat, 8> Worklist(InputFloats);
1610 const bool HasSNaN =
1611 any_of(Range&: InputVec, P: [](const APFloat *V) { return V->isSignaling(); });
1612 while (Worklist.size() > 1) {
1613 size_t LHSIdx = 0;
1614 size_t RHSIdx = 1;
1615 if (HasSNaN) {
1616 LHSIdx = Ctx.getRandomUInt64() % Worklist.size();
1617 RHSIdx = Ctx.getRandomUInt64() % (Worklist.size() - 1);
1618 if (RHSIdx >= LHSIdx)
1619 ++RHSIdx;
1620 }
1621
1622 APFloat Res =
1623 IID == Intrinsic::vector_reduce_fmax
1624 ? maxnumWithSNaNQuieting(LHS: Worklist[LHSIdx], RHS: Worklist[RHSIdx])
1625 : minnumWithSNaNQuieting(LHS: Worklist[LHSIdx], RHS: Worklist[RHSIdx]);
1626 if (LHSIdx < RHSIdx)
1627 std::swap(a&: LHSIdx, b&: RHSIdx);
1628 Worklist.erase(CI: Worklist.begin() + LHSIdx);
1629 Worklist.erase(CI: Worklist.begin() + RHSIdx);
1630 Worklist.push_back(Elt: std::move(Res));
1631 }
1632
1633 AnyValue ValidatedRes =
1634 handleFMFFlags(Val: Worklist.front(), FMF, /*IsInput=*/false);
1635 if (ValidatedRes.isPoison())
1636 return AnyValue::poison();
1637 APFloat FRes = handleDenormal(Val: ValidatedRes.asFloat(), Mode: DenormMode.Output,
1638 /*IsInput=*/false);
1639
1640 return applyNaNPropagation(Result: FRes, Inputs: InputVec);
1641 }
1642 case Intrinsic::fabs: {
1643 return visitBitwiseFPUnOpWithResult(
1644 RetTy, FMF, Operand: Args[0],
1645 ScalarFn: [](const APFloat &Operand) -> APFloat { return abs(X: Operand); });
1646 }
1647 case Intrinsic::fma: {
1648 return visitFPTriOpWithResult(
1649 RetTy, FMF, Op1: Args[0], Op2: Args[1], Op3: Args[2],
1650 ScalarFn: [](const APFloat &Op1, const APFloat &Op2,
1651 const APFloat &Op3) -> APFloat {
1652 auto Res = Op1;
1653 Res.fusedMultiplyAdd(Multiplicand: Op2, Addend: Op3, RM: RoundingMode::NearestTiesToEven);
1654 return Res;
1655 });
1656 }
1657 case Intrinsic::fmuladd: {
1658 return visitFPTriOpWithResult(
1659 RetTy, FMF, Op1: Args[0], Op2: Args[1], Op3: Args[2],
1660 ScalarFn: [&](const APFloat &Op1, const APFloat &Op2,
1661 const APFloat &Op3) -> APFloat {
1662 if (Ctx.fuseMultiplyAdd()) {
1663 auto Res = Op1;
1664 Res.fusedMultiplyAdd(Multiplicand: Op2, Addend: Op3, RM: RoundingMode::NearestTiesToEven);
1665 return Res;
1666 }
1667 return Op1 * Op2 + Op3;
1668 });
1669 }
1670 case Intrinsic::is_fpclass: {
1671 const FPClassTest Mask =
1672 static_cast<FPClassTest>(Args[1].asInteger().getZExtValue());
1673 return computeUnOp(Ty: RetTy, Operand: Args[0], ScalarFn: [&](const AnyValue &Op) -> AnyValue {
1674 if (Op.isPoison())
1675 return AnyValue::poison();
1676 return AnyValue::boolean(
1677 Val: static_cast<bool>(Op.asFloat().classify() & Mask));
1678 });
1679 }
1680 case Intrinsic::copysign: {
1681 return computeBinOp(
1682 Ty: RetTy, LHS: Args[0], RHS: Args[1],
1683 ScalarFn: [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
1684 if (LHS.isPoison() || RHS.isPoison())
1685 return AnyValue::poison();
1686 const AnyValue ValidatedLHS =
1687 handleFMFFlags(Val: LHS, FMF, /*IsInput=*/true);
1688 const AnyValue ValidatedRHS =
1689 handleFMFFlags(Val: RHS, FMF, /*IsInput=*/true);
1690 if (ValidatedLHS.isPoison() || ValidatedRHS.isPoison())
1691 return AnyValue::poison();
1692
1693 return handleFMFFlags(Val: APFloat::copySign(Value: ValidatedLHS.asFloat(),
1694 Sign: ValidatedRHS.asFloat()),
1695 FMF, /*IsInput=*/false);
1696 });
1697 }
1698 case Intrinsic::maxnum:
1699 case Intrinsic::minnum:
1700 case Intrinsic::maximum:
1701 case Intrinsic::minimum:
1702 case Intrinsic::maximumnum:
1703 case Intrinsic::minimumnum: {
1704 return visitFPBinOpWithResult(
1705 RetTy, FMF, LHS: Args[0], RHS: Args[1],
1706 ScalarFn: [&](const APFloat &LHS, const APFloat &RHS) -> APFloat {
1707 switch (IID) {
1708 case Intrinsic::maximum:
1709 return maximum(A: LHS, B: RHS);
1710 case Intrinsic::minimum:
1711 return minimum(A: LHS, B: RHS);
1712 case Intrinsic::maximumnum:
1713 return maximumnum(A: LHS, B: RHS);
1714 case Intrinsic::minimumnum:
1715 return minimumnum(A: LHS, B: RHS);
1716 case Intrinsic::maxnum:
1717 return maxnumWithSNaNQuieting(LHS, RHS);
1718 case Intrinsic::minnum:
1719 return minnumWithSNaNQuieting(LHS, RHS);
1720 default:
1721 llvm_unreachable("Unexpected intrinsic ID");
1722 }
1723 });
1724 }
1725 case Intrinsic::fptosi_sat:
1726 case Intrinsic::fptoui_sat: {
1727 const auto BitWidth = RetTy->getScalarSizeInBits();
1728 return computeUnOp(Ty: RetTy, Operand: Args[0], ScalarFn: [&](const AnyValue &Op) -> AnyValue {
1729 if (Op.isPoison())
1730 return AnyValue::poison();
1731 const APFloat &Operand = Op.asFloat();
1732 APSInt V(BitWidth, IID == Intrinsic::fptoui_sat);
1733 [[maybe_unused]] bool IsExact;
1734 Operand.convertToInteger(Result&: V, RM: APFloat::rmTowardZero, IsExact: &IsExact);
1735 return V;
1736 });
1737 }
1738 case Intrinsic::memcpy:
1739 case Intrinsic::memcpy_inline:
1740 case Intrinsic::memmove:
1741 return callMemTransferIntrinsic(CB, Args, IID);
1742 case Intrinsic::memset:
1743 case Intrinsic::memset_inline:
1744 return callMemSetIntrinsic(CB, Args);
1745 case Intrinsic::experimental_noalias_scope_decl:
1746 // FIXME: Not implemented yet. Currently it acts as a noop.
1747 return AnyValue();
1748 case Intrinsic::experimental_cttz_elts: {
1749 auto *IsZeroPoisonC = cast<ConstantInt>(Val: CB.getArgOperand(i: 1));
1750 const bool IsZeroPoison = IsZeroPoisonC->isOne();
1751
1752 const auto &Vec = Args[0].asAggregate();
1753 const unsigned RetBW = RetTy->getIntegerBitWidth();
1754
1755 if (!isUIntN(N: RetBW, x: Vec.size()))
1756 return AnyValue::poison();
1757
1758 uint64_t Count = 0;
1759 for (const AnyValue &V : Vec) {
1760 if (V.isPoison())
1761 return AnyValue::poison();
1762 if (!V.asInteger().isZero())
1763 break;
1764 ++Count;
1765 }
1766
1767 if (Count == Vec.size() && IsZeroPoison)
1768 return AnyValue::poison();
1769 return APInt(RetBW, Count);
1770 }
1771 case Intrinsic::experimental_get_vector_length: {
1772 auto *VFC = cast<ConstantInt>(Val: CB.getArgOperand(i: 1));
1773 auto *ScalableC = cast<ConstantInt>(Val: CB.getArgOperand(i: 2));
1774
1775 if (Args[0].isPoison())
1776 return AnyValue::poison();
1777
1778 const APInt &Cnt = Args[0].asInteger();
1779 const uint64_t VF = VFC->getZExtValue();
1780 const bool Scalable = ScalableC->isOne();
1781
1782 const uint64_t MaxLanes = Ctx.getEVL(EC: ElementCount::get(MinVal: VF, Scalable));
1783
1784 uint64_t Res = 0;
1785 if (!Cnt.isZero()) {
1786 if (Cnt.getActiveBits() <= 64 && Cnt.getZExtValue() <= MaxLanes) {
1787 Res = Cnt.getZExtValue();
1788 } else {
1789 APInt Max(Cnt.getBitWidth(), MaxLanes);
1790 APInt NumIters =
1791 APIntOps::RoundingUDiv(A: Cnt, B: Max, RM: APInt::Rounding::UP);
1792 uint64_t Lower =
1793 APIntOps::RoundingUDiv(A: Cnt, B: NumIters, RM: APInt::Rounding::UP)
1794 .getZExtValue();
1795 uint64_t Range = MaxLanes - Lower + 1;
1796 Res = Lower + Ctx.getRandomUInt64() % Range;
1797 }
1798 }
1799
1800 if (isIntN(N: 32, x: Res))
1801 return APInt(32, Res);
1802 return AnyValue::poison();
1803 }
1804
1805 case Intrinsic::experimental_vector_extract_last_active: {
1806 const auto &Data = Args[0].asAggregate();
1807 const AnyValue &Mask = Args[1];
1808
1809 for (size_t I = Data.size(); I != 0; --I) {
1810 switch (getMaskLane(Mask, I: I - 1)) {
1811 case BooleanKind::True:
1812 return Data[I - 1];
1813 case BooleanKind::False:
1814 break;
1815 case BooleanKind::Poison:
1816 return AnyValue::poison();
1817 }
1818 }
1819
1820 return Args[2];
1821 }
1822
1823 case Intrinsic::experimental_vector_compress: {
1824 const auto &Val = Args[0].asAggregate();
1825 const AnyValue &Mask = Args[1];
1826 const auto &Passthru = Args[2].asAggregate();
1827
1828 std::vector<AnyValue> Res;
1829 Res.reserve(n: Val.size());
1830
1831 for (size_t I = 0, E = Val.size(); I != E; ++I) {
1832 switch (getMaskLane(Mask, I)) {
1833 case BooleanKind::True:
1834 Res.push_back(x: Val[I]);
1835 break;
1836 case BooleanKind::False:
1837 break;
1838 case BooleanKind::Poison:
1839 return AnyValue::getPoisonValue(Ctx, Ty: RetTy);
1840 }
1841 }
1842
1843 for (size_t I = Res.size(), E = Val.size(); I != E; ++I)
1844 Res.push_back(x: Passthru[I]);
1845 return std::move(Res);
1846 }
1847
1848 case Intrinsic::experimental_vector_match: {
1849 const auto &Search = Args[0].asAggregate();
1850 const auto &Needles = Args[1].asAggregate();
1851 const auto &Mask = Args[2].asAggregate();
1852
1853 std::vector<AnyValue> Res;
1854 Res.reserve(n: Search.size());
1855
1856 for (size_t I = 0, E = Search.size(); I != E; ++I) {
1857 switch (Mask[I].asBoolean()) {
1858 case BooleanKind::False:
1859 Res.push_back(x: AnyValue::boolean(Val: false));
1860 continue;
1861 case BooleanKind::Poison:
1862 Res.push_back(x: AnyValue::poison());
1863 continue;
1864 case BooleanKind::True:
1865 break;
1866 }
1867
1868 if (Search[I].isPoison()) {
1869 Res.push_back(x: AnyValue::poison());
1870 continue;
1871 }
1872
1873 bool Found = false;
1874 bool SawPoison = false;
1875 for (const AnyValue &Needle : Needles) {
1876 if (Needle.isPoison()) {
1877 SawPoison = true;
1878 break;
1879 }
1880 if (Search[I].asInteger() == Needle.asInteger())
1881 Found = true;
1882 }
1883
1884 if (SawPoison)
1885 Res.push_back(x: AnyValue::poison());
1886 else
1887 Res.push_back(x: AnyValue::boolean(Val: Found));
1888 }
1889
1890 return std::move(Res);
1891 }
1892 case Intrinsic::experimental_vector_histogram_add:
1893 case Intrinsic::experimental_vector_histogram_uadd_sat:
1894 case Intrinsic::experimental_vector_histogram_umax:
1895 case Intrinsic::experimental_vector_histogram_umin:
1896 return callExperimentalVectorHistogramIntrinsic(CB, Args, IID);
1897 default:
1898 Handler.onUnrecognizedInstruction(I&: CB);
1899 setFailed();
1900 return AnyValue();
1901 }
1902 }
1903
1904 AnyValue callLibFunc(CallBase &CB, Function *ResolvedCallee,
1905 ArrayRef<AnyValue> CalleeArgs) {
1906 LibFunc LF = CurrentFrame->TLI.getLibFunc(FDecl: *ResolvedCallee);
1907 // Respect nobuiltin attributes on call site.
1908 if (CB.isNoBuiltin() || LF == NotLibFunc) {
1909 Handler.onUnrecognizedInstruction(I&: CB);
1910 setFailed();
1911 return AnyValue();
1912 }
1913
1914 if (auto LibCallRes =
1915 Lib.executeLibcall(LF, Name: CB.getName(), Type: CB.getType(), Args: CalleeArgs))
1916 return *LibCallRes;
1917
1918 if (ExitInfo)
1919 return AnyValue();
1920
1921 Handler.onUnrecognizedInstruction(I&: CB);
1922 setFailed();
1923 return AnyValue();
1924 }
1925
1926 /// Handle both poison-generating and UB-implying attributes for parameters
1927 /// and return values.
1928 void handleAttributes(Type *Ty, AnyValue &V, AttributeSet AttrsAtCallSite,
1929 AttributeSet AttrsAtCallee) {
1930 if (Ty->isIntOrIntVectorTy()) {
1931 if (auto CRAttr = AttrsAtCallSite.getAttribute(Kind: Attribute::Range);
1932 CRAttr.isValid())
1933 applyRangeAttr(V, CR: CRAttr.getRange());
1934 if (auto CRAttr = AttrsAtCallee.getAttribute(Kind: Attribute::Range);
1935 CRAttr.isValid())
1936 applyRangeAttr(V, CR: CRAttr.getRange());
1937 }
1938 if (AttributeFuncs::isNoFPClassCompatibleType(Ty)) {
1939 if (auto CRAttr = AttrsAtCallSite.getAttribute(Kind: Attribute::NoFPClass);
1940 CRAttr.isValid())
1941 applyNoFPClassAttr(V, NoFPClass: CRAttr.getNoFPClass());
1942 if (auto CRAttr = AttrsAtCallee.getAttribute(Kind: Attribute::NoFPClass);
1943 CRAttr.isValid())
1944 applyNoFPClassAttr(V, NoFPClass: CRAttr.getNoFPClass());
1945 }
1946 if (Ty->isPointerTy()) {
1947 if (AttrsAtCallSite.hasAttribute(Kind: Attribute::NonNull) ||
1948 AttrsAtCallee.hasAttribute(Kind: Attribute::NonNull))
1949 applyNonNullAttr(V, AS: Ty->getPointerAddressSpace(), DL);
1950 }
1951 if (Ty->isPtrOrPtrVectorTy()) {
1952 if (MaybeAlign Align = AttrsAtCallSite.getAlignment())
1953 applyAlignAttr(V, Alignment: *Align);
1954 if (MaybeAlign Align = AttrsAtCallee.getAlignment())
1955 applyAlignAttr(V, Alignment: *Align);
1956 }
1957 if ((AttrsAtCallSite.hasAttribute(Kind: Attribute::NoUndef) ||
1958 AttrsAtCallee.hasAttribute(Kind: Attribute::NoUndef)) &&
1959 violatesNoUndefAttr(V)) {
1960 reportImmediateUB() << "The value " << V
1961 << " violates noundef attribute.";
1962 return;
1963 }
1964 if (Ty->isPointerTy()) {
1965 unsigned AS = Ty->getPointerAddressSpace();
1966 if (uint64_t DereferenceableBytes =
1967 std::max(a: AttrsAtCallSite.getDereferenceableBytes(),
1968 b: AttrsAtCallee.getDereferenceableBytes())) {
1969 if (violatesDereferenceableBytesAttr(V, Bytes: DereferenceableBytes,
1970 /*OrNull=*/false, AS, Ctx))
1971 reportImmediateUB()
1972 << "The value " << V << " violates dereferenceable("
1973 << DereferenceableBytes << ") attribute.";
1974 } else if (uint64_t DereferenceableOrNullBytes =
1975 std::max(a: AttrsAtCallSite.getDereferenceableOrNullBytes(),
1976 b: AttrsAtCallee.getDereferenceableOrNullBytes())) {
1977 if (violatesDereferenceableBytesAttr(V, Bytes: DereferenceableOrNullBytes,
1978 /*OrNull=*/true, AS, Ctx))
1979 reportImmediateUB() << "The value " << V
1980 << " violates "
1981 "dereferenceable_or_null("
1982 << DereferenceableOrNullBytes << ") attribute.";
1983 }
1984 }
1985 }
1986
1987 /// Handle both poison-generating and UB-implying metadata on instructions.
1988 void handleMetadata(Type *Ty, AnyValue &V, Instruction &I) {
1989 auto ExtractFirstIntOperand = [](const MDNode *Node) {
1990 return mdconst::extract<ConstantInt>(MD: Node->getOperand(I: 0))->getZExtValue();
1991 };
1992
1993 if (Ty->isIntOrIntVectorTy()) {
1994 if (MDNode *Ranges = I.getMetadata(KindID: LLVMContext::MD_range)) {
1995 SmallVector<ConstantRange> RangeList;
1996 for (uint32_t I = 0; I < Ranges->getNumOperands(); I += 2) {
1997 RangeList.emplace_back(
1998 Args: mdconst::extract<ConstantInt>(MD: Ranges->getOperand(I))->getValue(),
1999 Args: mdconst::extract<ConstantInt>(MD: Ranges->getOperand(I: I + 1))
2000 ->getValue());
2001 }
2002 forEachScalarValue(V, Visit: [&](AnyValue &Scalar) {
2003 if (!Scalar.isInteger())
2004 return;
2005 for (auto &CR : RangeList)
2006 if (CR.contains(Val: Scalar.asInteger()))
2007 return;
2008 Scalar = AnyValue::poison();
2009 });
2010 }
2011 }
2012 if (AttributeFuncs::isNoFPClassCompatibleType(Ty)) {
2013 if (const MDNode *NoFPClass = I.getMetadata(KindID: LLVMContext::MD_nofpclass)) {
2014 applyNoFPClassAttr(
2015 V, NoFPClass: static_cast<FPClassTest>(ExtractFirstIntOperand(NoFPClass)));
2016 }
2017 }
2018 if (Ty->isPointerTy()) {
2019 if (I.hasMetadata(KindID: LLVMContext::MD_nonnull))
2020 applyNonNullAttr(V, AS: Ty->getPointerAddressSpace(), DL);
2021 // Unlike align attributes, !align is only defined for pointer types.
2022 if (const MDNode *Alignment = I.getMetadata(KindID: LLVMContext::MD_align))
2023 applyAlignAttr(V, Alignment: Align(ExtractFirstIntOperand(Alignment)));
2024 }
2025 if (I.hasMetadata(KindID: LLVMContext::MD_noundef) && violatesNoUndefAttr(V)) {
2026 reportImmediateUB() << "The value " << V
2027 << " violates !noundef metadata.";
2028 return;
2029 }
2030 if (Ty->isPointerTy()) {
2031 unsigned AS = Ty->getPointerAddressSpace();
2032 if (const MDNode *DereferenceableBytes =
2033 I.getMetadata(KindID: LLVMContext::MD_dereferenceable)) {
2034 uint64_t Bytes = ExtractFirstIntOperand(DereferenceableBytes);
2035 if (violatesDereferenceableBytesAttr(V, Bytes,
2036 /*OrNull=*/false, AS, Ctx))
2037 reportImmediateUB()
2038 << "The value " << V << " violates !dereferenceable !{i64 "
2039 << Bytes << "} metadata.";
2040 } else if (const MDNode *DereferenceableOrNullBytes =
2041 I.getMetadata(KindID: LLVMContext::MD_dereferenceable_or_null)) {
2042 uint64_t Bytes = ExtractFirstIntOperand(DereferenceableOrNullBytes);
2043 if (violatesDereferenceableBytesAttr(V, Bytes,
2044 /*OrNull=*/true, AS, Ctx))
2045 reportImmediateUB()
2046 << "The value " << V << " violates !dereferenceable_or_null!{i64 "
2047 << Bytes << "} metadata.";
2048 }
2049 }
2050 }
2051
2052 void enterCall(CallBase &CB) {
2053 Function *Callee = CB.getCalledFunction();
2054 // TODO: handle initializes
2055 auto &CalleeArgs = CurrentFrame->CalleeArgs;
2056 assert(CalleeArgs.empty() &&
2057 "Forgot to call returnFromCallee before entering a new call.");
2058 for (Value *Arg : CB.args())
2059 CalleeArgs.push_back(Elt: getValue(V: Arg));
2060
2061 if (!Callee) {
2062 Value *CalledOperand = CB.getCalledOperand();
2063 if (isNoopInlineAsm(V: CalledOperand, RetTy: CB.getType())) {
2064 CurrentFrame->ResolvedCallee = nullptr;
2065 returnFromCallee();
2066 return;
2067 }
2068
2069 if (isa<InlineAsm>(Val: CalledOperand)) {
2070 Handler.onUnrecognizedInstruction(I&: CB);
2071 setFailed();
2072 return;
2073 }
2074
2075 auto &CalleeVal = getValue(V: CalledOperand);
2076 if (CalleeVal.isPoison()) {
2077 reportImmediateUB() << "Indirect call through poison function pointer.";
2078 return;
2079 }
2080 Callee = Ctx.getTargetFunction(Ptr: CalleeVal.asPointer());
2081 if (!Callee) {
2082 reportImmediateUB()
2083 << "Indirect call through invalid function pointer.";
2084 return;
2085 }
2086 if (Callee->getFunctionType() != CB.getFunctionType()) {
2087 reportImmediateUB() << "Indirect call through a function pointer with "
2088 "mismatched signature. Expected: "
2089 << *CB.getFunctionType()
2090 << ", Actual: " << *Callee->getFunctionType();
2091 return;
2092 }
2093 }
2094
2095 assert(Callee && "Expected a resolved callee function.");
2096 assert(
2097 Callee->getFunctionType() == CB.getFunctionType() &&
2098 "Expected the callee function type to match the call site signature.");
2099
2100 // Handle parameter attributes (Attributes from resolved callee should be
2101 // applied if available).
2102 for (auto [I, Arg] : enumerate(First: CB.args())) {
2103 Type *ArgTy = Arg->getType();
2104 AnyValue &ArgVal = CalleeArgs[I];
2105
2106 // CallBase::paramHasAttr also checks parameter attributes at known
2107 // callee. We do it explicitly to avoid duplication.
2108 AttributeSet AttrsAtCallSite = CB.getParamAttributes(ArgNo: I);
2109 AttributeSet AttrsAtCallee = Callee->getAttributes().getParamAttrs(ArgNo: I);
2110
2111 if (ArgTy->isPointerTy()) {
2112 auto *ByValTy = AttrsAtCallSite.getByValType();
2113 auto *ByValTyFromCallee = AttrsAtCallee.getByValType();
2114 if (ByValTy != ByValTyFromCallee) {
2115 reportImmediateUB()
2116 << "Mismatched byval attribute between callee and callsite.";
2117 return;
2118 }
2119 if (ByValTy) {
2120 if (ArgVal.isPoison()) {
2121 reportImmediateUB() << "Invalid poison byval pointer argument.";
2122 return;
2123 }
2124
2125 uint64_t Size = Ctx.getEffectiveTypeAllocSize(Ty: ByValTy);
2126 MaybeAlign AllocAlign = AttrsAtCallSite.getAlignment();
2127 // Ignore the alignment at the callsite when it is set on the callee.
2128 if (MaybeAlign CalleeAlign = AttrsAtCallee.getAlignment())
2129 AllocAlign = CalleeAlign;
2130 if (!AllocAlign.has_value()) {
2131 // If the alignment is not specified, we use the default ABI
2132 // alignment. This is the default behavior of
2133 // TargetLoweringBase::getByValTypeAlignment.
2134 AllocAlign = DL.getABITypeAlign(Ty: ByValTy);
2135 }
2136 assert(I < Callee->arg_size() &&
2137 "Byval pointers cannot be passed via variadic arguments.");
2138 auto Obj = Ctx.allocate(
2139 Size, Align: AllocAlign->value(), Name: Callee->getArg(i: I)->getName(),
2140 AS: ArgTy->getPointerAddressSpace(), InitKind: MemInitKind::Uninitialized,
2141 AllocKind: MemAllocKind::Stack);
2142 if (!Obj) {
2143 reportError()
2144 << "Insufficient stack space for byval pointer argument.";
2145 return;
2146 }
2147 if (auto [MO, Offset] = verifyMemAccess(
2148 Ptr: ArgVal.asPointer(), AccessSize: Size,
2149 Alignment: std::max(a: AllocAlign.value(),
2150 b: AttrsAtCallSite.getAlignment().valueOrOne()),
2151 /*IsStore=*/false);
2152 MO)
2153 copy(Range: MO->getBytes().slice(N: Offset, M: Size), Out: Obj->getBytes().begin());
2154 else
2155 return;
2156 CurrentFrame->CalleeByValArgs.push_back(Elt: Obj);
2157 ArgVal = Ctx.deriveFromMemoryObject(Obj: std::move(Obj));
2158 }
2159 }
2160 handleAttributes(Ty: ArgTy, V&: ArgVal, AttrsAtCallSite, AttrsAtCallee);
2161 }
2162
2163 CurrentFrame->ResolvedCallee = Callee;
2164 if (Callee->isIntrinsic()) {
2165 CurrentFrame->CalleeRetVal = callIntrinsic(CB, Args: CalleeArgs);
2166 returnFromCallee();
2167 return;
2168 } else if (Callee->isDeclaration()) {
2169 CurrentFrame->CalleeRetVal = callLibFunc(CB, ResolvedCallee: Callee, CalleeArgs);
2170 returnFromCallee();
2171 return;
2172 } else {
2173 uint32_t MaxStackDepth = Ctx.getMaxStackDepth();
2174 if (MaxStackDepth && CallStack.size() >= MaxStackDepth) {
2175 reportError() << "Maximum stack depth exceeded.";
2176 return;
2177 }
2178 assert(!Callee->empty() && "Expected a defined function.");
2179 // Suspend the current frame and push the callee frame onto the stack.
2180 ArrayRef<AnyValue> Args = CurrentFrame->CalleeArgs;
2181 AnyValue &RetVal = CurrentFrame->CalleeRetVal;
2182 CurrentFrame->State = FrameState::Pending;
2183 CallStack.emplace_back(args&: *Callee, args: &CB, args&: CurrentFrame, args&: Args, args&: RetVal,
2184 args: Ctx.getTLIImpl());
2185 }
2186 }
2187
2188 void visitCallInst(CallInst &CI) { enterCall(CB&: CI); }
2189
2190 void visitInvokeInst(InvokeInst &II) {
2191 // TODO: handle exceptions
2192 enterCall(CB&: II);
2193 }
2194
2195 void visitAdd(BinaryOperator &I) {
2196 visitIntBinOp(I, ScalarFn: [&](const APInt &LHS, const APInt &RHS) {
2197 return addNoWrap(LHS, RHS, HasNSW: I.hasNoSignedWrap(), HasNUW: I.hasNoUnsignedWrap());
2198 });
2199 }
2200
2201 void visitSub(BinaryOperator &I) {
2202 visitIntBinOp(I, ScalarFn: [&](const APInt &LHS, const APInt &RHS) {
2203 return subNoWrap(LHS, RHS, HasNSW: I.hasNoSignedWrap(), HasNUW: I.hasNoUnsignedWrap());
2204 });
2205 }
2206
2207 void visitMul(BinaryOperator &I) {
2208 visitIntBinOp(I, ScalarFn: [&](const APInt &LHS, const APInt &RHS) {
2209 return mulNoWrap(LHS, RHS, HasNSW: I.hasNoSignedWrap(), HasNUW: I.hasNoUnsignedWrap());
2210 });
2211 }
2212
2213 void visitSDiv(BinaryOperator &I) {
2214 visitBinOp(I, ScalarFn: [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
2215 // Priority: Immediate UB > poison > normal value
2216 if (RHS.isPoison()) {
2217 reportImmediateUB() << "Division by zero (refine RHS to 0).";
2218 return AnyValue::poison();
2219 }
2220 const APInt &RHSVal = RHS.asInteger();
2221 if (RHSVal.isZero()) {
2222 reportImmediateUB() << "Division by zero.";
2223 return AnyValue::poison();
2224 }
2225 if (LHS.isPoison()) {
2226 if (RHSVal.isAllOnes())
2227 reportImmediateUB()
2228 << "Signed division overflow (refine LHS to INT_MIN).";
2229 return AnyValue::poison();
2230 }
2231 const APInt &LHSVal = LHS.asInteger();
2232 if (LHSVal.isMinSignedValue() && RHSVal.isAllOnes()) {
2233 reportImmediateUB() << "Signed division overflow.";
2234 return AnyValue::poison();
2235 }
2236
2237 if (I.isExact()) {
2238 APInt Q, R;
2239 APInt::sdivrem(LHS: LHSVal, RHS: RHSVal, Quotient&: Q, Remainder&: R);
2240 if (!R.isZero())
2241 return AnyValue::poison();
2242 return Q;
2243 } else {
2244 return LHSVal.sdiv(RHS: RHSVal);
2245 }
2246 });
2247 }
2248
2249 void visitSRem(BinaryOperator &I) {
2250 visitBinOp(I, ScalarFn: [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
2251 // Priority: Immediate UB > poison > normal value
2252 if (RHS.isPoison()) {
2253 reportImmediateUB() << "Division by zero (refine RHS to 0).";
2254 return AnyValue::poison();
2255 }
2256 const APInt &RHSVal = RHS.asInteger();
2257 if (RHSVal.isZero()) {
2258 reportImmediateUB() << "Division by zero.";
2259 return AnyValue::poison();
2260 }
2261 if (LHS.isPoison()) {
2262 if (RHSVal.isAllOnes())
2263 reportImmediateUB()
2264 << "Signed division overflow (refine LHS to INT_MIN).";
2265 return AnyValue::poison();
2266 }
2267 const APInt &LHSVal = LHS.asInteger();
2268 if (LHSVal.isMinSignedValue() && RHSVal.isAllOnes()) {
2269 reportImmediateUB() << "Signed division overflow. LHS: " << LHSVal
2270 << ", RHS: " << RHSVal;
2271 return AnyValue::poison();
2272 }
2273
2274 return LHSVal.srem(RHS: RHSVal);
2275 });
2276 }
2277
2278 void visitUDiv(BinaryOperator &I) {
2279 visitBinOp(I, ScalarFn: [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
2280 // Priority: Immediate UB > poison > normal value
2281 if (RHS.isPoison()) {
2282 reportImmediateUB() << "Division by zero (refine RHS to 0).";
2283 return AnyValue::poison();
2284 }
2285 const APInt &RHSVal = RHS.asInteger();
2286 if (RHSVal.isZero()) {
2287 reportImmediateUB() << "Division by zero.";
2288 return AnyValue::poison();
2289 }
2290 if (LHS.isPoison())
2291 return AnyValue::poison();
2292 const APInt &LHSVal = LHS.asInteger();
2293
2294 if (I.isExact()) {
2295 APInt Q, R;
2296 APInt::udivrem(LHS: LHSVal, RHS: RHSVal, Quotient&: Q, Remainder&: R);
2297 if (!R.isZero())
2298 return AnyValue::poison();
2299 return Q;
2300 } else {
2301 return LHSVal.udiv(RHS: RHSVal);
2302 }
2303 });
2304 }
2305
2306 void visitURem(BinaryOperator &I) {
2307 visitBinOp(I, ScalarFn: [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
2308 // Priority: Immediate UB > poison > normal value
2309 if (RHS.isPoison()) {
2310 reportImmediateUB() << "Division by zero (refine RHS to 0).";
2311 return AnyValue::poison();
2312 }
2313 const APInt &RHSVal = RHS.asInteger();
2314 if (RHSVal.isZero()) {
2315 reportImmediateUB() << "Division by zero.";
2316 return AnyValue::poison();
2317 }
2318 if (LHS.isPoison())
2319 return AnyValue::poison();
2320 const APInt &LHSVal = LHS.asInteger();
2321 return LHSVal.urem(RHS: RHSVal);
2322 });
2323 }
2324
2325 void visitFAdd(BinaryOperator &I) {
2326 visitFPBinOp(I, ScalarFn: [](const APFloat &LHS, const APFloat &RHS) -> APFloat {
2327 APFloat Res = LHS;
2328 Res.add(RHS, RM: APFloat::rmNearestTiesToEven);
2329 return Res;
2330 });
2331 }
2332
2333 void visitFSub(BinaryOperator &I) {
2334 visitFPBinOp(I, ScalarFn: [](const APFloat &LHS, const APFloat &RHS) -> APFloat {
2335 APFloat Res = LHS;
2336 Res.subtract(RHS, RM: APFloat::rmNearestTiesToEven);
2337 return Res;
2338 });
2339 }
2340
2341 void visitFMul(BinaryOperator &I) {
2342 visitFPBinOp(I, ScalarFn: [](const APFloat &LHS, const APFloat &RHS) -> APFloat {
2343 APFloat Res = LHS;
2344 Res.multiply(RHS, RM: APFloat::rmNearestTiesToEven);
2345 return Res;
2346 });
2347 }
2348
2349 void visitFDiv(BinaryOperator &I) {
2350 visitFPBinOp(I, ScalarFn: [](const APFloat &LHS, const APFloat &RHS) -> APFloat {
2351 APFloat Res = LHS;
2352 Res.divide(RHS, RM: APFloat::rmNearestTiesToEven);
2353 return Res;
2354 });
2355 }
2356
2357 void visitFRem(BinaryOperator &I) {
2358 visitFPBinOp(I, ScalarFn: [](const APFloat &LHS, const APFloat &RHS) -> APFloat {
2359 APFloat Res = LHS;
2360 Res.mod(RHS);
2361 return Res;
2362 });
2363 }
2364
2365 void visitFNeg(UnaryOperator &I) {
2366 visitBitwiseFPUnOp(
2367 I, ScalarFn: [](const APFloat &Operand) -> APFloat { return -Operand; });
2368 }
2369
2370 void visitTruncInst(TruncInst &Trunc) {
2371 visitIntUnOp(I&: Trunc, ScalarFn: [&](const APInt &Operand) -> AnyValue {
2372 unsigned DestBW = Trunc.getType()->getScalarSizeInBits();
2373 if (Trunc.hasNoSignedWrap() && Operand.getSignificantBits() > DestBW)
2374 return AnyValue::poison();
2375 if (Trunc.hasNoUnsignedWrap() && Operand.getActiveBits() > DestBW)
2376 return AnyValue::poison();
2377 return Operand.trunc(width: DestBW);
2378 });
2379 }
2380
2381 void visitZExtInst(ZExtInst &ZExt) {
2382 visitIntUnOp(I&: ZExt, ScalarFn: [&](const APInt &Operand) -> AnyValue {
2383 uint32_t DestBW = ZExt.getDestTy()->getScalarSizeInBits();
2384 if (ZExt.hasNonNeg() && Operand.isNegative())
2385 return AnyValue::poison();
2386 return Operand.zext(width: DestBW);
2387 });
2388 }
2389
2390 void visitSExtInst(SExtInst &SExt) {
2391 visitIntUnOp(I&: SExt, ScalarFn: [&](const APInt &Operand) -> AnyValue {
2392 uint32_t DestBW = SExt.getDestTy()->getScalarSizeInBits();
2393 return Operand.sext(width: DestBW);
2394 });
2395 }
2396
2397 void visitFPExtInst(FPExtInst &FPExt) { visitFPConvInst(I&: FPExt); }
2398
2399 void visitFPTruncInst(FPTruncInst &FPTrunc) { visitFPConvInst(I&: FPTrunc); }
2400
2401 void visitFPConvInst(Instruction &I) {
2402 if (!Ctx.isDefaultFPEnv())
2403 reportImmediateUB() << "Non-constrained floating-point operation assumes "
2404 "default floating-point environment";
2405
2406 const fltSemantics &DstSem =
2407 I.getType()->getScalarType()->getFltSemantics();
2408
2409 visitUnOp(I, ScalarFn: [&](const AnyValue &Operand) -> AnyValue {
2410 if (Operand.isPoison())
2411 return AnyValue::poison();
2412
2413 FastMathFlags FMF = cast<FPMathOperator>(Val&: I).getFastMathFlags();
2414 DenormalMode DenormMode =
2415 getCurrentDenormalMode(Ty: I.getOperand(i: 0)->getType());
2416
2417 auto ValidatedOperand = handleFMFFlags(Val: Operand, FMF, /*IsInput=*/true);
2418 if (ValidatedOperand.isPoison())
2419 return ValidatedOperand;
2420
2421 APFloat FOperand = handleDenormal(Val: ValidatedOperand.asFloat(),
2422 Mode: DenormMode.Input, /*IsInput=*/true);
2423 APFloat SourceNaN = FOperand;
2424
2425 bool LosesInfo;
2426 FOperand.convert(ToSemantics: DstSem, RM: Ctx.getCurrentRoundingMode(), losesInfo: &LosesInfo);
2427
2428 if (auto ValidateRes = handleFMFFlags(Val: FOperand, FMF, /*IsInput=*/false);
2429 ValidateRes.isPoison())
2430 return ValidateRes;
2431
2432 FOperand = handleDenormal(Val: std::move(FOperand), Mode: DenormMode.Output, IsInput: true);
2433
2434 return AnyValue(applyNaNPropagation(Result: FOperand, Inputs: {&SourceNaN}));
2435 });
2436 }
2437
2438 void visitFPToSIInst(FPToSIInst &FPToSI) {
2439 visitFPToIntInst(I&: FPToSI, /*IsUnsigned=*/false);
2440 }
2441
2442 void visitFPToUIInst(FPToUIInst &FPToUI) {
2443 visitFPToIntInst(I&: FPToUI, /*IsUnsigned=*/true);
2444 }
2445
2446 void visitFPToIntInst(Instruction &I, bool IsUnsigned) {
2447 // Note: We DO NOT use CurrentRoundingMode here.
2448 // Language specs require truncation towards zero for FP-to-Int conversions.
2449 visitUnOp(I, ScalarFn: [&](const AnyValue &Operand) -> AnyValue {
2450 if (Operand.isPoison())
2451 return AnyValue::poison();
2452
2453 APSInt Res(I.getType()->getScalarSizeInBits(), /*isUnsigned=*/IsUnsigned);
2454 bool IsExact;
2455 APFloat::opStatus Status = Operand.asFloat().convertToInteger(
2456 Result&: Res, RM: APFloat::rmTowardZero, IsExact: &IsExact);
2457
2458 if (Status == APFloat::opInvalidOp)
2459 return AnyValue::poison();
2460
2461 return AnyValue(Res);
2462 });
2463 }
2464
2465 void visitSIToFPInst(SIToFPInst &SIToFP) {
2466 visitIntToFPInst(I&: SIToFP, /*IsSigned=*/true);
2467 }
2468
2469 void visitUIToFPInst(UIToFPInst &UIToFP) {
2470 visitIntToFPInst(I&: UIToFP, /*IsSigned=*/false);
2471 }
2472
2473 void visitIntToFPInst(Instruction &I, bool IsSigned) {
2474 const fltSemantics &DstSem =
2475 I.getType()->getScalarType()->getFltSemantics();
2476
2477 visitUnOp(I, ScalarFn: [&](const AnyValue &Operand) -> AnyValue {
2478 if (Operand.isPoison())
2479 return AnyValue::poison();
2480
2481 APInt IOperand = Operand.asInteger();
2482
2483 if (isa<UIToFPInst>(Val: I) && I.hasNonNeg() && IOperand.isNegative())
2484 return AnyValue::poison();
2485
2486 APFloat Res(DstSem);
2487
2488 Res.convertFromAPInt(Input: Operand.asInteger(), /*IsSigned=*/IsSigned,
2489 RM: Ctx.getCurrentRoundingMode());
2490
2491 return AnyValue(Res);
2492 });
2493 }
2494
2495 void visitAnd(BinaryOperator &I) {
2496 visitIntBinOp(I, ScalarFn: [](const APInt &LHS, const APInt &RHS) -> AnyValue {
2497 return LHS & RHS;
2498 });
2499 }
2500
2501 void visitXor(BinaryOperator &I) {
2502 visitIntBinOp(I, ScalarFn: [](const APInt &LHS, const APInt &RHS) -> AnyValue {
2503 return LHS ^ RHS;
2504 });
2505 }
2506
2507 void visitOr(BinaryOperator &I) {
2508 visitIntBinOp(I, ScalarFn: [&](const APInt &LHS, const APInt &RHS) -> AnyValue {
2509 if (cast<PossiblyDisjointInst>(Val&: I).isDisjoint() && LHS.intersects(RHS))
2510 return AnyValue::poison();
2511 return LHS | RHS;
2512 });
2513 }
2514
2515 void visitShl(BinaryOperator &I) {
2516 visitIntBinOp(I, ScalarFn: [&](const APInt &LHS, const APInt &RHS) -> AnyValue {
2517 if (RHS.uge(RHS: LHS.getBitWidth()))
2518 return AnyValue::poison();
2519 if (I.hasNoSignedWrap() && RHS.uge(RHS: LHS.getNumSignBits()))
2520 return AnyValue::poison();
2521 if (I.hasNoUnsignedWrap() && RHS.ugt(RHS: LHS.countl_zero()))
2522 return AnyValue::poison();
2523 return LHS.shl(ShiftAmt: RHS);
2524 });
2525 }
2526
2527 void visitLShr(BinaryOperator &I) {
2528 visitIntBinOp(I, ScalarFn: [&](const APInt &LHS, const APInt &RHS) -> AnyValue {
2529 if (RHS.uge(RHS: LHS.getBitWidth()) ||
2530 (cast<PossiblyExactOperator>(Val&: I).isExact() &&
2531 RHS.ugt(RHS: LHS.countr_zero())))
2532 return AnyValue::poison();
2533 return LHS.lshr(ShiftAmt: RHS);
2534 });
2535 }
2536
2537 void visitAShr(BinaryOperator &I) {
2538 visitIntBinOp(I, ScalarFn: [&](const APInt &LHS, const APInt &RHS) -> AnyValue {
2539 if (RHS.uge(RHS: LHS.getBitWidth()) ||
2540 (cast<PossiblyExactOperator>(Val&: I).isExact() &&
2541 RHS.ugt(RHS: LHS.countr_zero())))
2542 return AnyValue::poison();
2543 return LHS.ashr(ShiftAmt: RHS);
2544 });
2545 }
2546
2547 void visitICmpInst(ICmpInst &I) {
2548 visitBinOp(I, ScalarFn: [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
2549 if (LHS.isPoison() || RHS.isPoison())
2550 return AnyValue::poison();
2551 const APInt &LHSVal =
2552 LHS.isPointer() ? LHS.asPointer().address() : LHS.asInteger();
2553 const APInt &RHSVal =
2554 RHS.isPointer() ? RHS.asPointer().address() : RHS.asInteger();
2555 if (I.hasSameSign() && LHSVal.isNonNegative() != RHSVal.isNonNegative())
2556 return AnyValue::poison();
2557 return AnyValue::boolean(
2558 Val: ICmpInst::compare(LHS: LHSVal, RHS: RHSVal, Pred: I.getPredicate()));
2559 });
2560 }
2561
2562 void visitFCmpInst(FCmpInst &I) {
2563 DenormalMode DenormMode =
2564 getCurrentDenormalMode(Ty: I.getOperand(i_nocapture: 0)->getType());
2565 FastMathFlags FMF = I.getFastMathFlags();
2566
2567 visitBinOp(I, ScalarFn: [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
2568 if (LHS.isPoison() || RHS.isPoison())
2569 return AnyValue::poison();
2570
2571 if (auto ValidateRes = handleFMFFlags(Val: LHS, FMF, /*IsInput=*/true);
2572 ValidateRes.isPoison())
2573 return ValidateRes;
2574 if (auto ValidateRes = handleFMFFlags(Val: RHS, FMF, /*IsInput=*/true);
2575 ValidateRes.isPoison())
2576 return ValidateRes;
2577
2578 APFloat FLHS =
2579 handleDenormal(Val: LHS.asFloat(), Mode: DenormMode.Input, /*IsInput=*/true);
2580 APFloat FRHS =
2581 handleDenormal(Val: RHS.asFloat(), Mode: DenormMode.Input, /*IsInput=*/true);
2582
2583 return AnyValue::boolean(Val: FCmpInst::compare(LHS: FLHS, RHS: FRHS, Pred: I.getPredicate()));
2584 });
2585 }
2586
2587 void visitSelect(SelectInst &SI) {
2588 AnyValue Res;
2589
2590 if (SI.getCondition()->getType()->isIntegerTy(BitWidth: 1)) {
2591 switch (getValue(V: SI.getCondition()).asBoolean()) {
2592 case BooleanKind::True:
2593 Res = getValue(V: SI.getTrueValue());
2594 break;
2595 case BooleanKind::False:
2596 Res = getValue(V: SI.getFalseValue());
2597 break;
2598 case BooleanKind::Poison:
2599 Res = AnyValue::getPoisonValue(Ctx, Ty: SI.getType());
2600 break;
2601 }
2602 } else {
2603 auto &Cond = getValue(V: SI.getCondition()).asAggregate();
2604 auto &TV = getValue(V: SI.getTrueValue()).asAggregate();
2605 auto &FV = getValue(V: SI.getFalseValue()).asAggregate();
2606 std::vector<AnyValue> ResVec;
2607 size_t Len = Cond.size();
2608 ResVec.reserve(n: Len);
2609 for (uint32_t I = 0; I != Len; ++I) {
2610 switch (Cond[I].asBoolean()) {
2611 case BooleanKind::True:
2612 ResVec.push_back(x: TV[I]);
2613 break;
2614 case BooleanKind::False:
2615 ResVec.push_back(x: FV[I]);
2616 break;
2617 case BooleanKind::Poison:
2618 ResVec.push_back(
2619 x: AnyValue::getPoisonValue(Ctx, Ty: SI.getType()->getScalarType()));
2620 break;
2621 }
2622 }
2623 Res = AnyValue(std::move(ResVec));
2624 }
2625
2626 // Handle fast-math flags
2627 if (auto *FPMO = dyn_cast<FPMathOperator>(Val: &SI)) {
2628 if (FastMathFlags FMF = FPMO->getFastMathFlags(); FMF.any())
2629 Res = handleFMFFlags(Val: std::move(Res), FMF, /*IsInput=*/true);
2630 }
2631
2632 setResult(I&: SI, V: std::move(Res));
2633 }
2634
2635 void visitAllocaInst(AllocaInst &AI) {
2636 uint64_t AllocSize = Ctx.getEffectiveTypeSize(Size: AI.getAllocationBaseSize(DL));
2637 if (AI.isArrayAllocation()) {
2638 auto &Size = getValue(V: AI.getArraySize());
2639 if (Size.isPoison()) {
2640 reportImmediateUB() << "Alloca with poison array size.";
2641 return;
2642 }
2643 if (Size.asInteger().getActiveBits() > 64) {
2644 reportImmediateUB()
2645 << "Alloca with large array size that overflows uint64_t. Size: "
2646 << Size.asInteger();
2647 return;
2648 }
2649 bool Overflowed = false;
2650 AllocSize = SaturatingMultiply(X: AllocSize, Y: Size.asInteger().getZExtValue(),
2651 ResultOverflowed: &Overflowed);
2652 if (Overflowed) {
2653 reportImmediateUB()
2654 << "Alloca with allocation size that overflows uint64_t. Size: "
2655 << Size.asInteger();
2656 return;
2657 }
2658 }
2659 // If it is used by llvm.lifetime.start, it should be initially dead.
2660 bool IsInitiallyDead = any_of(Range: AI.users(), P: [](User *U) {
2661 return match(V: U, P: m_Intrinsic<Intrinsic::lifetime_start>());
2662 });
2663 auto Obj = Ctx.allocate(Size: AllocSize, Align: AI.getPointerAlignment(DL).value(),
2664 Name: AI.getName(), AS: AI.getAddressSpace(),
2665 InitKind: IsInitiallyDead ? MemInitKind::Poisoned
2666 : MemInitKind::Uninitialized,
2667 AllocKind: MemAllocKind::Stack);
2668 if (!Obj) {
2669 reportError() << "Insufficient stack space.";
2670 return;
2671 }
2672 CurrentFrame->Allocas.push_back(Elt: Obj);
2673 setResult(I&: AI, V: Ctx.deriveFromMemoryObject(Obj));
2674 }
2675
2676 void visitGetElementPtrInst(GetElementPtrInst &GEP) {
2677 setResult(I&: GEP, V: Ctx.computeGEP(GEP&: cast<GEPOperator>(Val&: GEP),
2678 GetValue: [this](Value *V) -> const AnyValue & {
2679 return getValue(V);
2680 }));
2681 }
2682
2683 void visitPtrToInt(PtrToIntInst &I) {
2684 unsigned BitWidth = I.getType()->getScalarSizeInBits();
2685 return visitUnOp(I, ScalarFn: [this, BitWidth](const AnyValue &V) -> AnyValue {
2686 if (V.isPoison())
2687 return AnyValue::poison();
2688 Ctx.exposeProvenance(Prov&: V.asPointer().provenance());
2689 return V.asPointer().address().zextOrTrunc(width: BitWidth);
2690 });
2691 }
2692
2693 void visitIntToPtr(IntToPtrInst &I) {
2694 return visitUnOp(I, ScalarFn: [&](const AnyValue &V) -> AnyValue {
2695 if (V.isPoison())
2696 return AnyValue::poison();
2697 auto Prov = Ctx.getWildcardProvenance();
2698 // TODO: check metadata
2699 return Pointer(std::move(Prov),
2700 V.asInteger().zextOrTrunc(width: DL.getPointerSizeInBits(
2701 AS: I.getType()->getPointerAddressSpace())));
2702 });
2703 }
2704
2705 void visitPtrToAddr(PtrToAddrInst &I) {
2706 unsigned BitWidth = I.getType()->getScalarSizeInBits();
2707 return visitUnOp(I, ScalarFn: [&](const AnyValue &V) -> AnyValue {
2708 if (V.isPoison())
2709 return AnyValue::poison();
2710 return V.asPointer().address().trunc(width: BitWidth);
2711 });
2712 }
2713
2714 void visitLoadInst(LoadInst &LI) {
2715 auto RetVal = load(Ptr: getValue(V: LI.getPointerOperand()), Alignment: LI.getAlign(),
2716 ValTy: LI.getType(), NoUndef: LI.hasMetadata(KindID: LLVMContext::MD_noundef));
2717 // TODO: track volatile loads
2718 handleMetadata(Ty: LI.getType(), V&: RetVal, I&: LI);
2719 setResult(I&: LI, V: std::move(RetVal));
2720 }
2721
2722 void visitStoreInst(StoreInst &SI) {
2723 auto &Ptr = getValue(V: SI.getPointerOperand());
2724 auto &Val = getValue(V: SI.getValueOperand());
2725 // TODO: track volatile stores
2726 // TODO: handle metadata
2727 store(Ptr, Alignment: SI.getAlign(), Val, ValTy: SI.getValueOperand()->getType());
2728 if (!hasProgramExited() && !Handler.onInstructionExecuted(I&: SI, Result: AnyValue()))
2729 setFailed();
2730 }
2731
2732 void visitInstruction(Instruction &I) {
2733 Handler.onUnrecognizedInstruction(I);
2734 setFailed();
2735 }
2736
2737 void visitExtractValueInst(ExtractValueInst &EVI) {
2738 auto &Res = getValue(V: EVI.getAggregateOperand());
2739 const AnyValue *Pos = &Res;
2740 for (unsigned Idx : EVI.indices())
2741 Pos = &Pos->asAggregate()[Idx];
2742 setResult(I&: EVI, V: *Pos);
2743 }
2744
2745 void visitInsertValueInst(InsertValueInst &IVI) {
2746 AnyValue Res = getValue(V: IVI.getAggregateOperand());
2747 AnyValue *Pos = &Res;
2748 for (unsigned Idx : IVI.indices())
2749 Pos = &Pos->asAggregate()[Idx];
2750 *Pos = getValue(V: IVI.getInsertedValueOperand());
2751 setResult(I&: IVI, V: std::move(Res));
2752 }
2753
2754 void visitInsertElementInst(InsertElementInst &IEI) {
2755 auto Res = getValue(V: IEI.getOperand(i_nocapture: 0));
2756 auto &ResVec = Res.asAggregate();
2757 auto &Idx = getValue(V: IEI.getOperand(i_nocapture: 2));
2758 if (Idx.isPoison() || Idx.asInteger().uge(RHS: ResVec.size())) {
2759 setResult(I&: IEI, V: AnyValue::getPoisonValue(Ctx, Ty: IEI.getType()));
2760 return;
2761 }
2762 ResVec[Idx.asInteger().getZExtValue()] = getValue(V: IEI.getOperand(i_nocapture: 1));
2763 setResult(I&: IEI, V: std::move(Res));
2764 }
2765
2766 void visitExtractElementInst(ExtractElementInst &EEI) {
2767 auto &SrcVec = getValue(V: EEI.getOperand(i_nocapture: 0)).asAggregate();
2768 auto &Idx = getValue(V: EEI.getOperand(i_nocapture: 1));
2769 if (Idx.isPoison() || Idx.asInteger().uge(RHS: SrcVec.size())) {
2770 setResult(I&: EEI, V: AnyValue::getPoisonValue(Ctx, Ty: EEI.getType()));
2771 return;
2772 }
2773 setResult(I&: EEI, V: SrcVec[Idx.asInteger().getZExtValue()]);
2774 }
2775
2776 void visitShuffleVectorInst(ShuffleVectorInst &SVI) {
2777 auto &LHSVec = getValue(V: SVI.getOperand(i_nocapture: 0)).asAggregate();
2778 auto &RHSVec = getValue(V: SVI.getOperand(i_nocapture: 1)).asAggregate();
2779 uint32_t Size = cast<VectorType>(Val: SVI.getOperand(i_nocapture: 0)->getType())
2780 ->getElementCount()
2781 .getKnownMinValue();
2782 std::vector<AnyValue> Res;
2783 uint32_t DstLen = Ctx.getEVL(EC: SVI.getType()->getElementCount());
2784 Res.reserve(n: DstLen);
2785 uint32_t Stride = SVI.getShuffleMask().size();
2786 // For scalable vectors, we need to repeat the shuffle mask until we fill
2787 // the destination vector.
2788 for (uint32_t Off = 0; Off != DstLen; Off += Stride) {
2789 for (int Idx : SVI.getShuffleMask()) {
2790 if (Idx == PoisonMaskElem)
2791 Res.push_back(
2792 x: AnyValue::getPoisonValue(Ctx, Ty: SVI.getType()->getScalarType()));
2793 else if (Idx < static_cast<int>(Size))
2794 Res.push_back(x: LHSVec[Idx]);
2795 else
2796 Res.push_back(x: RHSVec[Idx - Size]);
2797 }
2798 }
2799 setResult(I&: SVI, V: std::move(Res));
2800 }
2801
2802 void visitBitCastInst(BitCastInst &BCI) {
2803 // The conversion is done as if the value had been stored to memory and read
2804 // back as the target type.
2805 SmallVector<Byte> Bytes;
2806 Bytes.resize(N: Ctx.getEffectiveTypeStoreSize(Ty: BCI.getType()),
2807 NV: Byte::concrete(Val: 0));
2808 Ctx.toBytes(Val: getValue(V: BCI.getOperand(i_nocapture: 0)), Ty: BCI.getOperand(i_nocapture: 0)->getType(),
2809 Bytes);
2810 setResult(I&: BCI, V: Ctx.fromBytes(Bytes, Ty: BCI.getType()));
2811 }
2812
2813 void visitFreezeInst(FreezeInst &FI) {
2814 AnyValue Val = getValue(V: FI.getOperand(i_nocapture: 0));
2815 Ctx.freeze(Val, Ty: FI.getType());
2816 setResult(I&: FI, V: std::move(Val));
2817 }
2818
2819 /// This function implements the main interpreter loop.
2820 /// It handles function calls in a non-recursive manner to avoid stack
2821 /// overflows.
2822 ProgramExitInfo runMainLoop() {
2823 uint32_t MaxSteps = Ctx.getMaxSteps();
2824 uint32_t Steps = 0;
2825 while (!hasProgramExited() && !CallStack.empty()) {
2826 Frame &Top = CallStack.back();
2827 CurrentFrame = &Top;
2828 if (Top.State == FrameState::Entry) {
2829 Handler.onFunctionEntry(F&: Top.Func, Args: Top.Args, CallSite: Top.CallSite);
2830 } else {
2831 assert(Top.State == FrameState::Pending &&
2832 "Expected to return from a callee.");
2833 returnFromCallee();
2834 }
2835
2836 Top.State = FrameState::Running;
2837 // Interpreter loop inside a function
2838 while (!hasProgramExited()) {
2839 assert(Top.State == FrameState::Running &&
2840 "Expected to be in running state.");
2841 if (MaxSteps != 0 && Steps >= MaxSteps) {
2842 reportError() << "Exceeded maximum number of execution steps.";
2843 break;
2844 }
2845 ++Steps;
2846
2847 Instruction &I = *Top.PC;
2848 visit(I: &I);
2849 Ctx.resetNoncacheableConstantBuffer();
2850 if (hasProgramExited())
2851 break;
2852
2853 // A function call or return has occurred.
2854 // We need to exit the inner loop and switch to a different frame.
2855 if (Top.State != FrameState::Running)
2856 break;
2857
2858 // Otherwise, move to the next instruction if it is not a terminator.
2859 // For terminators, the PC is updated in the visit* method.
2860 if (!I.isTerminator())
2861 ++Top.PC;
2862 }
2863
2864 if (hasProgramExited())
2865 break;
2866
2867 if (Top.State == FrameState::Exit) {
2868 assert((Top.Func.getReturnType()->isVoidTy() || !Top.RetVal.isNone()) &&
2869 "Expected return value to be set on function exit.");
2870 Handler.onFunctionExit(F&: Top.Func, RetVal: Top.RetVal);
2871 // Free stack objects allocated in this frame.
2872 for (auto &Obj : Top.Allocas)
2873 Ctx.free(Obj: *Obj);
2874 CallStack.pop_back();
2875 } else {
2876 assert(Top.State == FrameState::Pending &&
2877 "Expected to enter a callee.");
2878 }
2879 }
2880 if (!hasProgramExited())
2881 requestProgramExit(Kind: ProgramExitInfo::ProgramExitKind::Returned);
2882 return *getExitInfo();
2883 }
2884};
2885
2886ProgramExitInfo Context::runFunction(Function &F, ArrayRef<AnyValue> Args,
2887 AnyValue &RetVal, EventHandler &Handler) {
2888 InstExecutor Executor(*this, Handler, F, Args, RetVal);
2889 return Executor.runMainLoop();
2890}
2891
2892} // namespace llvm::ubi
2893