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