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
922 /// Returns the oracle function if \p CB is an llvm.speculative.load in
923 /// oracle form, nullptr otherwise.
924 static Function *getSpeculativeLoadOracle(const CallBase &CB) {
925 return CB.getIntrinsicID() == Intrinsic::speculative_load
926 ? dyn_cast<Function>(Val: CB.getArgOperand(i: 2))
927 : nullptr;
928 }
929
930 AnyValue callSpeculativeLoadIntrinsic(CallBase &CB, const AnyValue &Ptr,
931 const AnyValue &NumBytes) {
932 Type *RetTy = CB.getType();
933 if (Ptr.isPoison()) {
934 reportImmediateUB() << "llvm.speculative.load with poison pointer.";
935 return AnyValue();
936 }
937 if (NumBytes.isPoison()) {
938 reportImmediateUB()
939 << "llvm.speculative.load with poison number of accessible bytes.";
940 return AnyValue();
941 }
942
943 const uint64_t Size = Ctx.getEffectiveTypeStoreSize(Ty: RetTy);
944 const APInt &NumBytesInt = NumBytes.asInteger();
945 if (NumBytesInt.ugt(RHS: Size)) {
946 reportImmediateUB() << "llvm.speculative.load number of accessible bytes "
947 << NumBytesInt.getZExtValue()
948 << " exceeds the loaded size " << Size << ".";
949 return AnyValue();
950 }
951
952 // Only the accessible bytes are read from memory and must be in bounds of
953 // the underlying object. All other bytes are poison.
954 const uint64_t N = NumBytesInt.getZExtValue();
955 SmallVector<Byte> Bytes(Size, Byte::poison());
956 if (N != 0) {
957 const bool FromEnd = cast<ConstantInt>(Val: CB.getArgOperand(i: 1))->isOne();
958 const uint64_t Start = FromEnd ? Size - N : 0;
959 const Pointer &PtrVal = Ptr.asPointer();
960 auto [MO, Offset] =
961 verifyMemAccess(Ptr: PtrVal.getWithNewAddr(NewAddr: PtrVal.address() + Start), AccessSize: N,
962 Alignment: Align(1), /*IsStore=*/false);
963 if (!MO)
964 return AnyValue();
965 copy(Range: MO->getBytes().slice(N: Offset, M: N), Out: Bytes.begin() + Start);
966 }
967 return Ctx.fromBytes(Bytes, Ty: RetTy);
968 }
969
970public:
971 InstExecutor(Context &C, EventHandler &H, Function &F,
972 ArrayRef<AnyValue> Args, AnyValue &RetVal)
973 : ExecutorBase(C, H), DL(Ctx.getDataLayout()),
974 Lib(Ctx, Handler, DL, static_cast<ExecutorBase &>(*this)) {
975 CallStack.emplace_back(args&: F, /*CallSite=*/args: nullptr, /*LastFrame=*/args: nullptr, args&: Args,
976 args&: RetVal, args: Ctx.getTLIImpl());
977 }
978
979 void visitReturnInst(ReturnInst &RI) {
980 if (auto *RV = RI.getReturnValue())
981 CurrentFrame->RetVal = getValue(V: RV);
982 else
983 CurrentFrame->RetVal = AnyValue();
984 CurrentFrame->State = FrameState::Exit;
985 if (!Handler.onInstructionExecuted(I&: RI, Result: None))
986 setFailed();
987 }
988
989 void visitUncondBrInst(UncondBrInst &BI) { jumpTo(Terminator&: BI, DestBB: BI.getSuccessor()); }
990
991 void visitCondBrInst(CondBrInst &BI) {
992 switch (getValue(V: BI.getCondition()).asBoolean()) {
993 case BooleanKind::True:
994 jumpTo(Terminator&: BI, DestBB: BI.getSuccessor(i: 0));
995 return;
996 case BooleanKind::False:
997 jumpTo(Terminator&: BI, DestBB: BI.getSuccessor(i: 1));
998 return;
999 case BooleanKind::Poison:
1000 reportImmediateUB() << "Branch on poison condition.";
1001 return;
1002 }
1003 }
1004
1005 void visitSwitchInst(SwitchInst &SI) {
1006 auto &Cond = getValue(V: SI.getCondition());
1007 if (Cond.isPoison()) {
1008 reportImmediateUB() << "Switch on poison condition.";
1009 return;
1010 }
1011 for (auto &Case : SI.cases()) {
1012 if (Case.getCaseValue()->getValue() == Cond.asInteger()) {
1013 jumpTo(Terminator&: SI, DestBB: Case.getCaseSuccessor());
1014 return;
1015 }
1016 }
1017 jumpTo(Terminator&: SI, DestBB: SI.getDefaultDest());
1018 }
1019
1020 void visitUnreachableInst(UnreachableInst &) {
1021 reportImmediateUB() << "Unreachable code.";
1022 }
1023
1024 void visitCallBrInst(CallBrInst &CI) {
1025 if (isNoopInlineAsm(V: CI.getCalledOperand(), RetTy: CI.getType())) {
1026 jumpTo(Terminator&: CI, DestBB: CI.getDefaultDest());
1027 return;
1028 }
1029
1030 Handler.onUnrecognizedInstruction(I&: CI);
1031 setFailed();
1032 }
1033
1034 void visitIndirectBrInst(IndirectBrInst &IBI) {
1035 auto &Target = getValue(V: IBI.getAddress());
1036 if (Target.isPoison()) {
1037 reportImmediateUB() << "Indirect branch on poison.";
1038 return;
1039 }
1040 if (BasicBlock *DestBB = Ctx.getTargetBlock(Ptr: Target.asPointer())) {
1041 if (any_of(Range: IBI.successors(),
1042 P: [DestBB](BasicBlock *Succ) { return Succ == DestBB; }))
1043 jumpTo(Terminator&: IBI, DestBB);
1044 else
1045 reportImmediateUB() << "Indirect branch on unlisted target BB.";
1046
1047 return;
1048 }
1049 reportImmediateUB() << "Indirect branch on invalid target BB.";
1050 }
1051
1052 void returnFromCallee() {
1053 auto &CB = cast<CallBase>(Val&: *CurrentFrame->PC);
1054 AnyValue &RetVal = CurrentFrame->CalleeRetVal;
1055 if (Function *Oracle = getSpeculativeLoadOracle(CB)) {
1056 // RetVal is the oracle's result; use it to complete the load.
1057 handleAttributes(Ty: Oracle->getReturnType(), V&: RetVal, AttrsAtCallSite: AttributeSet(),
1058 AttrsAtCallee: Oracle->getAttributes().getRetAttrs());
1059 RetVal =
1060 callSpeculativeLoadIntrinsic(CB, Ptr: CurrentFrame->CalleeArgs[0], NumBytes: RetVal);
1061 if (hasProgramExited())
1062 return;
1063 }
1064 CurrentFrame->CalleeArgs.clear();
1065 if (Type *RetTy = CB.getType(); !RetTy->isVoidTy()) {
1066 // Handle attributes on the return value (Attributes from resolved callee
1067 // should be applied if available).
1068 AttributeSet AttrsAtCallSite = CB.getRetAttributes();
1069 AttributeSet AttrsAtCallee =
1070 CurrentFrame->ResolvedCallee->getAttributes().getRetAttrs();
1071 handleAttributes(Ty: RetTy, V&: RetVal, AttrsAtCallSite, AttrsAtCallee);
1072 handleMetadata(Ty: RetTy, V&: RetVal, I&: CB);
1073 }
1074 setResult(I&: CB, V: std::move(RetVal));
1075
1076 for (auto &ByValArg : CurrentFrame->CalleeByValArgs)
1077 Ctx.free(Obj: *ByValArg);
1078 CurrentFrame->CalleeByValArgs.clear();
1079
1080 if (auto *II = dyn_cast<InvokeInst>(Val: &CB))
1081 jumpTo(Terminator&: *II, DestBB: II->getNormalDest());
1082 else if (CurrentFrame->State == FrameState::Pending)
1083 ++CurrentFrame->PC;
1084 }
1085
1086 AnyValue callIntrinsic(CallBase &CB, ArrayRef<AnyValue> Args) {
1087 Intrinsic::ID IID = CB.getIntrinsicID();
1088 Type *RetTy = CB.getType();
1089 const FastMathFlags FMF = CB.getFastMathFlagsOrNone();
1090
1091 switch (IID) {
1092 case Intrinsic::assume:
1093 switch (Args[0].asBoolean()) {
1094 case BooleanKind::True:
1095 for (unsigned Idx = 0; Idx < CB.getNumOperandBundles(); Idx++) {
1096 OperandBundleUse OBU = CB.getOperandBundleAt(Index: Idx);
1097 auto GetBundleArg = [&](uint32_t Offset) -> Value * {
1098 return OBU.Inputs[Offset];
1099 };
1100 if (OBU.Inputs.empty())
1101 continue;
1102 Value *WasOnVal = GetBundleArg(0);
1103 // Bail out on unrecognized operand bundles.
1104 if (!WasOnVal->getType()->isPointerTy())
1105 continue;
1106 unsigned AS = WasOnVal->getType()->getPointerAddressSpace();
1107 const AnyValue &WasOn = getValue(V: WasOnVal);
1108 if (WasOn.isPoison()) {
1109 reportImmediateUB() << "Assume on poison pointer.";
1110 break;
1111 }
1112 const Pointer &WasOnPtr = WasOn.asPointer();
1113 Attribute::AttrKind Kind =
1114 Attribute::getAttrKindFromName(AttrName: OBU.getTagName());
1115 switch (Kind) {
1116 case Attribute::Alignment: {
1117 // Alignment assumptions should have 2 or 3 arguments.
1118 APInt Alignment = getIntNonPoison(V: getValue(V: GetBundleArg(1)));
1119 APInt CheckedAddr = WasOnPtr.address();
1120 if (OBU.Inputs.size() == 3) {
1121 APInt Offset = getIntNonPoison(V: getValue(V: GetBundleArg(2)));
1122 CheckedAddr -= Offset.sextOrTrunc(width: CheckedAddr.getBitWidth());
1123 }
1124 if (!Alignment.isPowerOf2()) {
1125 if (!CheckedAddr.isZero())
1126 reportImmediateUB() << "Assume on pointer " << WasOn
1127 << " with a nonzero adjusted address and a "
1128 "non-power-of-two alignment "
1129 << Alignment << '.';
1130 break;
1131 }
1132 if (CheckedAddr.countr_zero() < Alignment.logBase2())
1133 reportImmediateUB()
1134 << "The pointer " << WasOn << " violates align(" << Alignment
1135 << ") assumption.";
1136 break;
1137 }
1138 case Attribute::NonNull:
1139 if (WasOnPtr.isNullPtr(AS, DL))
1140 reportImmediateUB()
1141 << "The pointer " << WasOn << " violates nonnull assumption.";
1142 break;
1143 case Attribute::Dereferenceable:
1144 case Attribute::DereferenceableOrNull: {
1145 APInt DereferenceableBytes =
1146 getIntNonPoison(V: getValue(V: GetBundleArg(1)));
1147 // Only n > 0 implies that the pointer is dereferenceable.
1148 if (DereferenceableBytes.isZero())
1149 break;
1150 if (violatesDereferenceableBytesAttr(
1151 V: WasOn, Bytes: DereferenceableBytes.getLimitedValue(),
1152 OrNull: Kind == Attribute::DereferenceableOrNull, AS, Ctx))
1153 reportImmediateUB() << "The pointer " << WasOn << " violates "
1154 << (Kind == Attribute::DereferenceableOrNull
1155 ? "dereferenceable_or_null("
1156 : "dereferenceable(")
1157 << DereferenceableBytes << ") assumption.";
1158 break;
1159 }
1160 default:
1161 // TODO: handle other operand bundles like separate_storage.
1162 break;
1163 }
1164 }
1165 break;
1166 case BooleanKind::False:
1167 case BooleanKind::Poison:
1168 reportImmediateUB() << "Assume on false or poison condition.";
1169 break;
1170 }
1171 return AnyValue();
1172 case Intrinsic::lifetime_start:
1173 case Intrinsic::lifetime_end: {
1174 auto Ptr = Args[0];
1175 if (Ptr.isPoison())
1176 return AnyValue();
1177 auto *MO = Ctx.checkProvenance(Ptr: Ptr.asPointer(),
1178 Check: [](const Provenance &) { return true; });
1179 assert(MO && "Memory object accessed by lifetime intrinsic should be "
1180 "always valid.");
1181 if (IID == Intrinsic::lifetime_start) {
1182 MO->setState(MemoryObjectState::Alive);
1183 fill(Range: MO->getBytes(), Value: Byte::undef());
1184 } else {
1185 fill(Range: MO->getBytes(), Value: Byte::poison());
1186 MO->setState(MemoryObjectState::Dead);
1187 }
1188 return AnyValue();
1189 }
1190 case Intrinsic::ssa_copy:
1191 case Intrinsic::expect:
1192 case Intrinsic::expect_with_probability:
1193 return Args[0];
1194 case Intrinsic::donothing:
1195 return AnyValue();
1196 case Intrinsic::vscale: {
1197 const unsigned BitWidth = RetTy->getScalarSizeInBits();
1198 const APInt VScale(64, Ctx.getVScale());
1199 if (!VScale.isIntN(N: BitWidth))
1200 return AnyValue::poison();
1201 return VScale.zextOrTrunc(width: BitWidth);
1202 }
1203 case Intrinsic::abs: {
1204 const bool IsIntMinPoison = getBooleanNonPoison(Boolean: Args[1].asBoolean());
1205 return visitIntUnOpWithResult(
1206 RetTy, Operand: Args[0], ScalarFn: [&](const APInt &Operand) -> AnyValue {
1207 if (IsIntMinPoison && Operand.isMinSignedValue())
1208 return AnyValue::poison();
1209 return Operand.abs();
1210 });
1211 }
1212 case Intrinsic::smax: {
1213 return visitIntBinOpWithResult(
1214 RetTy, LHS: Args[0], RHS: Args[1],
1215 ScalarFn: [](const APInt &LHS, const APInt &RHS) -> AnyValue {
1216 return APIntOps::smax(A: LHS, B: RHS);
1217 });
1218 }
1219 case Intrinsic::smin: {
1220 return visitIntBinOpWithResult(
1221 RetTy, LHS: Args[0], RHS: Args[1],
1222 ScalarFn: [](const APInt &LHS, const APInt &RHS) -> AnyValue {
1223 return APIntOps::smin(A: LHS, B: RHS);
1224 });
1225 }
1226 case Intrinsic::umax: {
1227 return visitIntBinOpWithResult(
1228 RetTy, LHS: Args[0], RHS: Args[1],
1229 ScalarFn: [](const APInt &LHS, const APInt &RHS) -> AnyValue {
1230 return APIntOps::umax(A: LHS, B: RHS);
1231 });
1232 }
1233 case Intrinsic::umin: {
1234 return visitIntBinOpWithResult(
1235 RetTy, LHS: Args[0], RHS: Args[1],
1236 ScalarFn: [](const APInt &LHS, const APInt &RHS) -> AnyValue {
1237 return APIntOps::umin(A: LHS, B: RHS);
1238 });
1239 }
1240 case Intrinsic::scmp:
1241 case Intrinsic::ucmp: {
1242 const unsigned BitWidth = RetTy->getScalarSizeInBits();
1243 return visitIntBinOpWithResult(
1244 RetTy, LHS: Args[0], RHS: Args[1],
1245 ScalarFn: [&](const APInt &LHS, const APInt &RHS) -> AnyValue {
1246 if (LHS == RHS)
1247 return APInt::getZero(numBits: BitWidth);
1248 if (IID == Intrinsic::scmp)
1249 return LHS.slt(RHS) ? APInt::getAllOnes(numBits: BitWidth)
1250 : APInt(BitWidth, 1);
1251 return LHS.ult(RHS) ? APInt::getAllOnes(numBits: BitWidth)
1252 : APInt(BitWidth, 1);
1253 });
1254 }
1255 case Intrinsic::bitreverse: {
1256 return visitIntUnOpWithResult(RetTy, Operand: Args[0],
1257 ScalarFn: [](const APInt &Operand) -> AnyValue {
1258 return Operand.reverseBits();
1259 });
1260 }
1261 case Intrinsic::bswap: {
1262 return visitIntUnOpWithResult(
1263 RetTy, Operand: Args[0],
1264 ScalarFn: [](const APInt &Operand) -> AnyValue { return Operand.byteSwap(); });
1265 }
1266 case Intrinsic::ctpop: {
1267 return visitIntUnOpWithResult(
1268 RetTy, Operand: Args[0], ScalarFn: [](const APInt &Operand) -> AnyValue {
1269 return APInt(Operand.getBitWidth(), Operand.popcount());
1270 });
1271 }
1272 case Intrinsic::ctlz:
1273 case Intrinsic::cttz: {
1274 const bool IsZeroPoison = getBooleanNonPoison(Boolean: Args[1].asBoolean());
1275 return visitIntUnOpWithResult(
1276 RetTy, Operand: Args[0], ScalarFn: [&](const APInt &Operand) -> AnyValue {
1277 if (IsZeroPoison && Operand.isZero())
1278 return AnyValue::poison();
1279 if (IID == Intrinsic::ctlz)
1280 return APInt(Operand.getBitWidth(), Operand.countl_zero());
1281 return APInt(Operand.getBitWidth(), Operand.countr_zero());
1282 });
1283 }
1284 case Intrinsic::fshl:
1285 case Intrinsic::fshr: {
1286 return visitIntTriOpWithResult(
1287 RetTy, Op1: Args[0], Op2: Args[1], Op3: Args[2],
1288 ScalarFn: [IID](const APInt &Op1, const APInt &Op2,
1289 const APInt &Op3) -> AnyValue {
1290 const unsigned BitWidth = Op1.getBitWidth();
1291 const uint64_t ShiftAmount = Op3.urem(RHS: BitWidth);
1292 const bool IsFShr = IID == Intrinsic::fshr;
1293 if (ShiftAmount == 0)
1294 return IsFShr ? Op2 : Op1;
1295 const uint64_t LShrAmount =
1296 IsFShr ? ShiftAmount : BitWidth - ShiftAmount;
1297 const uint64_t ShlAmount =
1298 !IsFShr ? ShiftAmount : BitWidth - ShiftAmount;
1299 return Op1.shl(shiftAmt: ShlAmount) | Op2.lshr(shiftAmt: LShrAmount);
1300 });
1301 }
1302 case Intrinsic::clmul: {
1303 return visitIntBinOpWithResult(
1304 RetTy, LHS: Args[0], RHS: Args[1],
1305 ScalarFn: [](const APInt &LHS, const APInt &RHS) -> AnyValue {
1306 return APIntOps::clmul(LHS, RHS);
1307 });
1308 }
1309 case Intrinsic::sadd_with_overflow:
1310 case Intrinsic::uadd_with_overflow:
1311 case Intrinsic::ssub_with_overflow:
1312 case Intrinsic::usub_with_overflow:
1313 case Intrinsic::smul_with_overflow:
1314 case Intrinsic::umul_with_overflow: {
1315 return visitOverflowIntBinOpWithResult(
1316 RetTy, LHS: Args[0], RHS: Args[1],
1317 ScalarFn: [IID](const APInt &LHS, const APInt &RHS) -> std::pair<APInt, bool> {
1318 APInt Res;
1319 bool Overflow = false;
1320 switch (IID) {
1321 case Intrinsic::sadd_with_overflow:
1322 Res = LHS.sadd_ov(RHS, Overflow);
1323 break;
1324 case Intrinsic::uadd_with_overflow:
1325 Res = LHS.uadd_ov(RHS, Overflow);
1326 break;
1327 case Intrinsic::ssub_with_overflow:
1328 Res = LHS.ssub_ov(RHS, Overflow);
1329 break;
1330 case Intrinsic::usub_with_overflow:
1331 Res = LHS.usub_ov(RHS, Overflow);
1332 break;
1333 case Intrinsic::smul_with_overflow:
1334 Res = LHS.smul_ov(RHS, Overflow);
1335 break;
1336 case Intrinsic::umul_with_overflow:
1337 Res = LHS.umul_ov(RHS, Overflow);
1338 break;
1339 default:
1340 llvm_unreachable("Unexpected intrinsic ID");
1341 }
1342 return {Res, Overflow};
1343 });
1344 }
1345 case Intrinsic::sadd_sat:
1346 case Intrinsic::uadd_sat:
1347 case Intrinsic::ssub_sat:
1348 case Intrinsic::usub_sat:
1349 case Intrinsic::sshl_sat:
1350 case Intrinsic::ushl_sat: {
1351 return visitIntBinOpWithResult(
1352 RetTy, LHS: Args[0], RHS: Args[1],
1353 ScalarFn: [IID](const APInt &LHS, const APInt &RHS) -> AnyValue {
1354 switch (IID) {
1355 case Intrinsic::sadd_sat:
1356 return LHS.sadd_sat(RHS);
1357 case Intrinsic::uadd_sat:
1358 return LHS.uadd_sat(RHS);
1359 case Intrinsic::ssub_sat:
1360 return LHS.ssub_sat(RHS);
1361 case Intrinsic::usub_sat:
1362 return LHS.usub_sat(RHS);
1363 case Intrinsic::sshl_sat: {
1364 if (RHS.uge(RHS: LHS.getBitWidth()))
1365 return AnyValue::poison();
1366 return LHS.sshl_sat(RHS);
1367 }
1368 case Intrinsic::ushl_sat: {
1369 if (RHS.uge(RHS: LHS.getBitWidth()))
1370 return AnyValue::poison();
1371 return LHS.ushl_sat(RHS);
1372 }
1373 default:
1374 llvm_unreachable("Unexpected intrinsic ID");
1375 }
1376 });
1377 }
1378 case Intrinsic::smulh:
1379 case Intrinsic::umulh:
1380 return visitIntBinOpWithResult(
1381 RetTy, LHS: Args[0], RHS: Args[1],
1382 ScalarFn: [IID](const APInt &LHS, const APInt &RHS) -> AnyValue {
1383 return IID == Intrinsic::smulh ? APIntOps::mulhs(C1: LHS, C2: RHS)
1384 : APIntOps::mulhu(C1: LHS, C2: RHS);
1385 });
1386 case Intrinsic::pdep:
1387 case Intrinsic::pext:
1388 return visitIntBinOpWithResult(
1389 RetTy, LHS: Args[0], RHS: Args[1],
1390 ScalarFn: [IID](const APInt &Val, const APInt &Mask) -> AnyValue {
1391 return IID == Intrinsic::pdep ? APIntOps::pdep(Val, Mask)
1392 : APIntOps::pext(Val, Mask);
1393 });
1394 case Intrinsic::vector_reduce_add:
1395 case Intrinsic::vector_reduce_mul:
1396 case Intrinsic::vector_reduce_and:
1397 case Intrinsic::vector_reduce_or:
1398 case Intrinsic::vector_reduce_xor:
1399 case Intrinsic::vector_reduce_smax:
1400 case Intrinsic::vector_reduce_smin:
1401 case Intrinsic::vector_reduce_umax:
1402 case Intrinsic::vector_reduce_umin: {
1403 std::optional<APInt> Res;
1404 for (const auto &V : Args[0].asAggregate()) {
1405 if (V.isPoison()) {
1406 Res.reset();
1407 break;
1408 }
1409 const auto &IntV = V.asInteger();
1410 if (!Res) {
1411 Res = IntV;
1412 continue;
1413 }
1414 switch (IID) {
1415 case Intrinsic::vector_reduce_add:
1416 *Res += IntV;
1417 break;
1418 case Intrinsic::vector_reduce_mul:
1419 *Res *= IntV;
1420 break;
1421 case Intrinsic::vector_reduce_and:
1422 *Res &= IntV;
1423 break;
1424 case Intrinsic::vector_reduce_or:
1425 *Res |= IntV;
1426 break;
1427 case Intrinsic::vector_reduce_xor:
1428 *Res ^= IntV;
1429 break;
1430 case Intrinsic::vector_reduce_smax:
1431 *Res = APIntOps::smax(A: *Res, B: IntV);
1432 break;
1433 case Intrinsic::vector_reduce_smin:
1434 *Res = APIntOps::smin(A: *Res, B: IntV);
1435 break;
1436 case Intrinsic::vector_reduce_umax:
1437 *Res = APIntOps::umax(A: *Res, B: IntV);
1438 break;
1439 case Intrinsic::vector_reduce_umin:
1440 *Res = APIntOps::umin(A: *Res, B: IntV);
1441 break;
1442 default:
1443 llvm_unreachable("Unexpected intrinsic ID");
1444 }
1445 }
1446 return Res ? *Res : AnyValue::poison();
1447 }
1448 case Intrinsic::vector_insert: {
1449 assert(!Args[2].isPoison() &&
1450 "Verifier should reject poison vector_insert immarg.");
1451 const auto &Vec = Args[0].asAggregate();
1452 const auto &SubVec = Args[1].asAggregate();
1453 const auto &Idx = Args[2].asInteger();
1454 auto EC =
1455 cast<VectorType>(Val: CB.getArgOperand(i: 1)->getType())->getElementCount();
1456 const uint64_t RawOffset = Idx.getZExtValue();
1457 const uint32_t MinSize = EC.getKnownMinValue();
1458 assert(RawOffset % MinSize == 0 &&
1459 "Verifier should reject misaligned vector_insert index.");
1460 const uint64_t Chunk = RawOffset / MinSize;
1461 const uint64_t EVL = Ctx.getEVL(EC);
1462 if (Chunk > std::numeric_limits<uint64_t>::max() / EVL)
1463 return AnyValue::getPoisonValue(Ctx, Ty: RetTy);
1464 const uint64_t Offset = Chunk * EVL;
1465 if (Offset > Vec.size() || SubVec.size() > Vec.size() - Offset)
1466 return AnyValue::getPoisonValue(Ctx, Ty: RetTy);
1467 std::vector<AnyValue> Res;
1468 Res.reserve(n: Vec.size());
1469 for (size_t I = 0; I != Vec.size(); ++I) {
1470 if (I >= Offset && I < Offset + SubVec.size())
1471 Res.push_back(x: SubVec[I - Offset]);
1472 else
1473 Res.push_back(x: Vec[I]);
1474 }
1475 return std::move(Res);
1476 }
1477 case Intrinsic::vector_extract: {
1478 assert(!Args[1].isPoison() &&
1479 "Verifier should reject poison vector_extract immarg.");
1480 const auto &Vec = Args[0].asAggregate();
1481 const auto &Idx = Args[1].asInteger();
1482 auto EC = cast<VectorType>(Val: RetTy)->getElementCount();
1483 const uint64_t RawOffset = Idx.getZExtValue();
1484 const uint32_t MinSize = EC.getKnownMinValue();
1485 assert(RawOffset % MinSize == 0 &&
1486 "Verifier should reject misaligned vector_extract index.");
1487 const uint64_t Chunk = RawOffset / MinSize;
1488 const uint64_t EVL = Ctx.getEVL(EC);
1489 if (Chunk > std::numeric_limits<uint64_t>::max() / EVL)
1490 return AnyValue::getPoisonValue(Ctx, Ty: RetTy);
1491 const uint64_t Offset = Chunk * EVL;
1492 if (Offset > Vec.size() || EVL > Vec.size() - Offset)
1493 return AnyValue::getPoisonValue(Ctx, Ty: RetTy);
1494 return std::vector<AnyValue>(Vec.begin() + Offset,
1495 Vec.begin() + Offset + EVL);
1496 }
1497 case Intrinsic::vector_reverse: {
1498 auto Vec = Args[0].asAggregate();
1499 std::reverse(first: Vec.begin(), last: Vec.end());
1500 return std::move(Vec);
1501 }
1502 case Intrinsic::vector_deinterleave2:
1503 case Intrinsic::vector_deinterleave3:
1504 case Intrinsic::vector_deinterleave4:
1505 case Intrinsic::vector_deinterleave5:
1506 case Intrinsic::vector_deinterleave6:
1507 case Intrinsic::vector_deinterleave7:
1508 case Intrinsic::vector_deinterleave8: {
1509 const unsigned Factor = getDeinterleaveIntrinsicFactor(ID: IID);
1510 if (Factor == 0)
1511 llvm_unreachable("Unexpected intrinsic ID");
1512 const auto &Vec = Args[0].asAggregate();
1513 std::vector<std::vector<AnyValue>> Res(Factor);
1514 for (auto &SubVec : Res)
1515 SubVec.reserve(n: Vec.size() / Factor);
1516 for (size_t I = 0, E = Vec.size(); I != E; ++I)
1517 Res[I % Factor].push_back(x: Vec[I]);
1518
1519 std::vector<AnyValue> AggRes;
1520 AggRes.reserve(n: Factor);
1521 for (auto &SubVec : Res)
1522 AggRes.emplace_back(args: std::move(SubVec));
1523 return AnyValue(std::move(AggRes));
1524 }
1525 case Intrinsic::vector_interleave2:
1526 case Intrinsic::vector_interleave3:
1527 case Intrinsic::vector_interleave4:
1528 case Intrinsic::vector_interleave5:
1529 case Intrinsic::vector_interleave6:
1530 case Intrinsic::vector_interleave7:
1531 case Intrinsic::vector_interleave8: {
1532 const unsigned Factor = getInterleaveIntrinsicFactor(ID: IID);
1533 if (Factor == 0)
1534 llvm_unreachable("Unexpected intrinsic ID");
1535 const auto &Vec = Args[0].asAggregate();
1536 std::vector<AnyValue> Res;
1537 Res.reserve(n: Vec.size() * Factor);
1538 for (size_t I = 0, E = Vec.size(); I != E; ++I) {
1539 for (unsigned J = 0; J != Factor; ++J)
1540 Res.push_back(x: Args[J].asAggregate()[I]);
1541 }
1542 return std::move(Res);
1543 }
1544 case Intrinsic::vector_splice_left: {
1545 if (Args[2].isPoison())
1546 return AnyValue::getPoisonValue(Ctx, Ty: RetTy);
1547 const auto &LHS = Args[0].asAggregate();
1548 const auto &RHS = Args[1].asAggregate();
1549 const auto &Off = Args[2].asInteger();
1550 const size_t Len = LHS.size();
1551 if (Off.ugt(RHS: Len))
1552 return AnyValue::getPoisonValue(Ctx, Ty: RetTy);
1553 uint64_t Offset = Off.getZExtValue();
1554 std::vector<AnyValue> Res;
1555 Res.reserve(n: Len);
1556 for (size_t I = 0; I != Len; ++I) {
1557 size_t Pos = I + Offset;
1558 Res.push_back(x: Pos < Len ? LHS[Pos] : RHS[Pos - Len]);
1559 }
1560 return std::move(Res);
1561 }
1562 case Intrinsic::vector_splice_right: {
1563 if (Args[2].isPoison())
1564 return AnyValue::getPoisonValue(Ctx, Ty: RetTy);
1565 const auto &LHS = Args[0].asAggregate();
1566 const auto &RHS = Args[1].asAggregate();
1567 const auto &Off = Args[2].asInteger();
1568 const size_t Len = LHS.size();
1569 if (Off.ugt(RHS: Len))
1570 return AnyValue::getPoisonValue(Ctx, Ty: RetTy);
1571 uint64_t Offset = Len - Off.getZExtValue();
1572 std::vector<AnyValue> Res;
1573 Res.reserve(n: Len);
1574 for (size_t I = 0; I != Len; ++I) {
1575 size_t Pos = I + Offset;
1576 Res.push_back(x: Pos < Len ? LHS[Pos] : RHS[Pos - Len]);
1577 }
1578 return std::move(Res);
1579 }
1580 case Intrinsic::stepvector: {
1581 std::vector<AnyValue> Res;
1582 const uint32_t Len =
1583 Ctx.getEVL(EC: cast<VectorType>(Val: RetTy)->getElementCount());
1584 const unsigned BitWidth = RetTy->getScalarSizeInBits();
1585 Res.reserve(n: Len);
1586 for (uint64_t I = 0; I != Len; ++I) {
1587 Res.push_back(
1588 x: APInt(BitWidth, I, /*IsSigned=*/false, /*ImplicitTrunc=*/true));
1589 }
1590 return std::move(Res);
1591 }
1592 case Intrinsic::vector_reduce_fadd:
1593 case Intrinsic::vector_reduce_fmul:
1594 case Intrinsic::vector_reduce_fmaximum:
1595 case Intrinsic::vector_reduce_fminimum:
1596 case Intrinsic::vector_reduce_fmaximumnum:
1597 case Intrinsic::vector_reduce_fminimumnum: {
1598 const auto DenormMode = getCurrentDenormalMode(Ty: RetTy);
1599 const bool HasStart = IID == Intrinsic::vector_reduce_fadd ||
1600 IID == Intrinsic::vector_reduce_fmul;
1601 const AnyValue &Vector = HasStart ? Args[1] : Args[0];
1602 std::optional<APFloat> Res;
1603 if (HasStart) {
1604 if (Args[0].isPoison())
1605 return AnyValue::poison();
1606 const AnyValue ValidatedStart =
1607 handleFMFFlags(Val: Args[0], FMF, /*IsInput=*/true);
1608 if (ValidatedStart.isPoison())
1609 return AnyValue::poison();
1610 Res = handleDenormal(Val: ValidatedStart.asFloat(), Mode: DenormMode.Input,
1611 /*IsInput=*/true);
1612 }
1613 for (const auto &V : Vector.asAggregate()) {
1614 if (V.isPoison())
1615 return AnyValue::poison();
1616 const AnyValue ValidatedOp = handleFMFFlags(Val: V, FMF, /*IsInput=*/true);
1617 if (ValidatedOp.isPoison())
1618 return AnyValue::poison();
1619 APFloat Op = handleDenormal(Val: ValidatedOp.asFloat(), Mode: DenormMode.Input,
1620 /*IsInput=*/true);
1621 if (!Res) {
1622 Res = std::move(Op);
1623 continue;
1624 }
1625 switch (IID) {
1626 case Intrinsic::vector_reduce_fadd:
1627 *Res = *Res + Op;
1628 break;
1629 case Intrinsic::vector_reduce_fmul:
1630 *Res = *Res * Op;
1631 break;
1632 case Intrinsic::vector_reduce_fmaximum:
1633 *Res = maximum(A: *Res, B: Op);
1634 break;
1635 case Intrinsic::vector_reduce_fminimum:
1636 *Res = minimum(A: *Res, B: Op);
1637 break;
1638 case Intrinsic::vector_reduce_fmaximumnum:
1639 *Res = maximumnum(A: *Res, B: Op);
1640 break;
1641 case Intrinsic::vector_reduce_fminimumnum:
1642 *Res = minimumnum(A: *Res, B: Op);
1643 break;
1644 default:
1645 llvm_unreachable("Unexpected intrinsic ID");
1646 }
1647 }
1648 assert(Res.has_value());
1649 const AnyValue ValidatedRes =
1650 handleFMFFlags(Val: *Res, FMF, /*IsInput=*/false);
1651 if (ValidatedRes.isPoison())
1652 return AnyValue::poison();
1653 const APFloat FRes =
1654 handleDenormal(Val: ValidatedRes.asFloat(), Mode: DenormMode.Output,
1655 /*IsInput=*/false);
1656 SmallVector<const APFloat *, 8> InputVec;
1657 InputVec.reserve(N: Vector.asAggregate().size());
1658 transform(
1659 Range: Vector.asAggregate(), d_first: std::back_inserter(x&: InputVec),
1660 F: [](const AnyValue &V) -> const APFloat * { return &V.asFloat(); });
1661 return applyNaNPropagation(Result: FRes, Inputs: InputVec);
1662 }
1663 case Intrinsic::vector_reduce_fmax:
1664 case Intrinsic::vector_reduce_fmin: {
1665 const auto DenormMode = getCurrentDenormalMode(Ty: RetTy);
1666 const auto &Vector = Args[0].asAggregate();
1667 SmallVector<APFloat, 8> InputFloats;
1668 SmallVector<const APFloat *, 8> InputVec;
1669 InputFloats.reserve(N: Vector.size());
1670 InputVec.reserve(N: Vector.size());
1671 for (const auto &V : Vector) {
1672 if (V.isPoison())
1673 return AnyValue::poison();
1674 const AnyValue ValidatedOp = handleFMFFlags(Val: V, FMF, /*IsInput=*/true);
1675 if (ValidatedOp.isPoison())
1676 return AnyValue::poison();
1677 InputFloats.push_back(Elt: handleDenormal(Val: ValidatedOp.asFloat(),
1678 Mode: DenormMode.Input,
1679 /*IsInput=*/true));
1680 InputVec.push_back(Elt: &InputFloats.back());
1681 }
1682 assert(!InputVec.empty());
1683 SmallVector<APFloat, 8> Worklist(InputFloats);
1684 const bool HasSNaN =
1685 any_of(Range&: InputVec, P: [](const APFloat *V) { return V->isSignaling(); });
1686 while (Worklist.size() > 1) {
1687 size_t LHSIdx = 0;
1688 size_t RHSIdx = 1;
1689 if (HasSNaN) {
1690 LHSIdx = Ctx.getRandomUInt64() % Worklist.size();
1691 RHSIdx = Ctx.getRandomUInt64() % (Worklist.size() - 1);
1692 if (RHSIdx >= LHSIdx)
1693 ++RHSIdx;
1694 }
1695
1696 APFloat Res =
1697 IID == Intrinsic::vector_reduce_fmax
1698 ? maxnumWithSNaNQuieting(LHS: Worklist[LHSIdx], RHS: Worklist[RHSIdx])
1699 : minnumWithSNaNQuieting(LHS: Worklist[LHSIdx], RHS: Worklist[RHSIdx]);
1700 if (LHSIdx < RHSIdx)
1701 std::swap(a&: LHSIdx, b&: RHSIdx);
1702 Worklist.erase(CI: Worklist.begin() + LHSIdx);
1703 Worklist.erase(CI: Worklist.begin() + RHSIdx);
1704 Worklist.push_back(Elt: std::move(Res));
1705 }
1706
1707 AnyValue ValidatedRes =
1708 handleFMFFlags(Val: Worklist.front(), FMF, /*IsInput=*/false);
1709 if (ValidatedRes.isPoison())
1710 return AnyValue::poison();
1711 APFloat FRes = handleDenormal(Val: ValidatedRes.asFloat(), Mode: DenormMode.Output,
1712 /*IsInput=*/false);
1713
1714 return applyNaNPropagation(Result: FRes, Inputs: InputVec);
1715 }
1716 case Intrinsic::fabs: {
1717 return visitBitwiseFPUnOpWithResult(
1718 RetTy, FMF, Operand: Args[0],
1719 ScalarFn: [](const APFloat &Operand) -> APFloat { return abs(X: Operand); });
1720 }
1721 case Intrinsic::fma: {
1722 return visitFPTriOpWithResult(
1723 RetTy, FMF, Op1: Args[0], Op2: Args[1], Op3: Args[2],
1724 ScalarFn: [](const APFloat &Op1, const APFloat &Op2,
1725 const APFloat &Op3) -> APFloat {
1726 auto Res = Op1;
1727 Res.fusedMultiplyAdd(Multiplicand: Op2, Addend: Op3, RM: RoundingMode::NearestTiesToEven);
1728 return Res;
1729 });
1730 }
1731 case Intrinsic::fmuladd: {
1732 return visitFPTriOpWithResult(
1733 RetTy, FMF, Op1: Args[0], Op2: Args[1], Op3: Args[2],
1734 ScalarFn: [&](const APFloat &Op1, const APFloat &Op2,
1735 const APFloat &Op3) -> APFloat {
1736 if (Ctx.fuseMultiplyAdd()) {
1737 auto Res = Op1;
1738 Res.fusedMultiplyAdd(Multiplicand: Op2, Addend: Op3, RM: RoundingMode::NearestTiesToEven);
1739 return Res;
1740 }
1741 return Op1 * Op2 + Op3;
1742 });
1743 }
1744 case Intrinsic::is_fpclass: {
1745 const FPClassTest Mask =
1746 static_cast<FPClassTest>(Args[1].asInteger().getZExtValue());
1747 return computeUnOp(Ty: RetTy, Operand: Args[0], ScalarFn: [&](const AnyValue &Op) -> AnyValue {
1748 if (Op.isPoison())
1749 return AnyValue::poison();
1750 return AnyValue::boolean(
1751 Val: static_cast<bool>(Op.asFloat().classify() & Mask));
1752 });
1753 }
1754 case Intrinsic::copysign: {
1755 return computeBinOp(
1756 Ty: RetTy, LHS: Args[0], RHS: Args[1],
1757 ScalarFn: [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
1758 if (LHS.isPoison() || RHS.isPoison())
1759 return AnyValue::poison();
1760 const AnyValue ValidatedLHS =
1761 handleFMFFlags(Val: LHS, FMF, /*IsInput=*/true);
1762 const AnyValue ValidatedRHS =
1763 handleFMFFlags(Val: RHS, FMF, /*IsInput=*/true);
1764 if (ValidatedLHS.isPoison() || ValidatedRHS.isPoison())
1765 return AnyValue::poison();
1766
1767 return handleFMFFlags(Val: APFloat::copySign(Value: ValidatedLHS.asFloat(),
1768 Sign: ValidatedRHS.asFloat()),
1769 FMF, /*IsInput=*/false);
1770 });
1771 }
1772 case Intrinsic::maxnum:
1773 case Intrinsic::minnum:
1774 case Intrinsic::maximum:
1775 case Intrinsic::minimum:
1776 case Intrinsic::maximumnum:
1777 case Intrinsic::minimumnum: {
1778 return visitFPBinOpWithResult(
1779 RetTy, FMF, LHS: Args[0], RHS: Args[1],
1780 ScalarFn: [&](const APFloat &LHS, const APFloat &RHS) -> APFloat {
1781 switch (IID) {
1782 case Intrinsic::maximum:
1783 return maximum(A: LHS, B: RHS);
1784 case Intrinsic::minimum:
1785 return minimum(A: LHS, B: RHS);
1786 case Intrinsic::maximumnum:
1787 return maximumnum(A: LHS, B: RHS);
1788 case Intrinsic::minimumnum:
1789 return minimumnum(A: LHS, B: RHS);
1790 case Intrinsic::maxnum:
1791 return maxnumWithSNaNQuieting(LHS, RHS);
1792 case Intrinsic::minnum:
1793 return minnumWithSNaNQuieting(LHS, RHS);
1794 default:
1795 llvm_unreachable("Unexpected intrinsic ID");
1796 }
1797 });
1798 }
1799 case Intrinsic::fptosi_sat:
1800 case Intrinsic::fptoui_sat: {
1801 const auto BitWidth = RetTy->getScalarSizeInBits();
1802 return computeUnOp(Ty: RetTy, Operand: Args[0], ScalarFn: [&](const AnyValue &Op) -> AnyValue {
1803 if (Op.isPoison())
1804 return AnyValue::poison();
1805 const APFloat &Operand = Op.asFloat();
1806 APSInt V(BitWidth, IID == Intrinsic::fptoui_sat);
1807 [[maybe_unused]] bool IsExact;
1808 Operand.convertToInteger(Result&: V, RM: APFloat::rmTowardZero, IsExact: &IsExact);
1809 return V;
1810 });
1811 }
1812 case Intrinsic::memcpy:
1813 case Intrinsic::memcpy_inline:
1814 case Intrinsic::memmove:
1815 return callMemTransferIntrinsic(CB, Args, IID);
1816 case Intrinsic::memset:
1817 case Intrinsic::memset_inline:
1818 return callMemSetIntrinsic(CB, Args);
1819 case Intrinsic::speculative_load:
1820 assert(!getSpeculativeLoadOracle(CB) &&
1821 "oracle form must be handled earlier");
1822 return callSpeculativeLoadIntrinsic(CB, Ptr: Args[0], NumBytes: Args[2]);
1823 case Intrinsic::experimental_noalias_scope_decl:
1824 // FIXME: Not implemented yet. Currently it acts as a noop.
1825 return AnyValue();
1826 case Intrinsic::experimental_cttz_elts: {
1827 auto *IsZeroPoisonC = cast<ConstantInt>(Val: CB.getArgOperand(i: 1));
1828 const bool IsZeroPoison = IsZeroPoisonC->isOne();
1829
1830 const auto &Vec = Args[0].asAggregate();
1831 const unsigned RetBW = RetTy->getIntegerBitWidth();
1832
1833 if (!isUIntN(N: RetBW, x: Vec.size()))
1834 return AnyValue::poison();
1835
1836 for (const AnyValue &V : Vec)
1837 if (V.isPoison())
1838 return AnyValue::poison();
1839
1840 uint64_t Count = 0;
1841 for (const AnyValue &V : Vec) {
1842 if (!V.asInteger().isZero())
1843 break;
1844 ++Count;
1845 }
1846
1847 if (Count == Vec.size() && IsZeroPoison)
1848 return AnyValue::poison();
1849 return APInt(RetBW, Count);
1850 }
1851 case Intrinsic::experimental_get_vector_length: {
1852 auto *VFC = cast<ConstantInt>(Val: CB.getArgOperand(i: 1));
1853 auto *ScalableC = cast<ConstantInt>(Val: CB.getArgOperand(i: 2));
1854
1855 if (Args[0].isPoison())
1856 return AnyValue::poison();
1857
1858 const APInt &Cnt = Args[0].asInteger();
1859 uint64_t MaxLanes = VFC->getZExtValue();
1860 if (ScalableC->isOne())
1861 MaxLanes *= Ctx.getVScale();
1862
1863 uint64_t Res = 0;
1864 if (!Cnt.isZero()) {
1865 if (Cnt.getActiveBits() <= 64 && Cnt.getZExtValue() <= MaxLanes) {
1866 Res = Cnt.getZExtValue();
1867 } else {
1868 APInt Max(Cnt.getBitWidth(), MaxLanes);
1869 APInt NumIters =
1870 APIntOps::RoundingUDiv(A: Cnt, B: Max, RM: APInt::Rounding::UP);
1871 uint64_t Lower =
1872 APIntOps::RoundingUDiv(A: Cnt, B: NumIters, RM: APInt::Rounding::UP)
1873 .getZExtValue();
1874 uint64_t Range = MaxLanes - Lower + 1;
1875 Res = Lower + Ctx.getRandomUInt64() % Range;
1876 }
1877 }
1878
1879 if (isIntN(N: 32, x: Res))
1880 return APInt(32, Res);
1881 return AnyValue::poison();
1882 }
1883
1884 case Intrinsic::experimental_vector_extract_last_active: {
1885 const auto &Data = Args[0].asAggregate();
1886 const AnyValue &Mask = Args[1];
1887
1888 for (size_t I = Data.size(); I != 0; --I) {
1889 switch (getMaskLane(Mask, I: I - 1)) {
1890 case BooleanKind::True:
1891 return Data[I - 1];
1892 case BooleanKind::False:
1893 break;
1894 case BooleanKind::Poison:
1895 return AnyValue::poison();
1896 }
1897 }
1898
1899 return Args[2];
1900 }
1901
1902 case Intrinsic::experimental_vector_compress: {
1903 const auto &Val = Args[0].asAggregate();
1904 const AnyValue &Mask = Args[1];
1905 const auto &Passthru = Args[2].asAggregate();
1906
1907 std::vector<AnyValue> Res;
1908 Res.reserve(n: Val.size());
1909
1910 for (size_t I = 0, E = Val.size(); I != E; ++I) {
1911 switch (getMaskLane(Mask, I)) {
1912 case BooleanKind::True:
1913 Res.push_back(x: Val[I]);
1914 break;
1915 case BooleanKind::False:
1916 break;
1917 case BooleanKind::Poison:
1918 return AnyValue::getPoisonValue(Ctx, Ty: RetTy);
1919 }
1920 }
1921
1922 for (size_t I = Res.size(), E = Val.size(); I != E; ++I)
1923 Res.push_back(x: Passthru[I]);
1924 return std::move(Res);
1925 }
1926
1927 case Intrinsic::experimental_vector_match: {
1928 const auto &Search = Args[0].asAggregate();
1929 const auto &Needles = Args[1].asAggregate();
1930 const auto &Mask = Args[2].asAggregate();
1931
1932 std::vector<AnyValue> Res;
1933 Res.reserve(n: Search.size());
1934
1935 for (size_t I = 0, E = Search.size(); I != E; ++I) {
1936 switch (Mask[I].asBoolean()) {
1937 case BooleanKind::False:
1938 Res.push_back(x: AnyValue::boolean(Val: false));
1939 continue;
1940 case BooleanKind::Poison:
1941 Res.push_back(x: AnyValue::poison());
1942 continue;
1943 case BooleanKind::True:
1944 break;
1945 }
1946
1947 if (Search[I].isPoison()) {
1948 Res.push_back(x: AnyValue::poison());
1949 continue;
1950 }
1951
1952 bool Found = false;
1953 bool SawPoison = false;
1954 for (const AnyValue &Needle : Needles) {
1955 if (Needle.isPoison()) {
1956 SawPoison = true;
1957 break;
1958 }
1959 if (Search[I].asInteger() == Needle.asInteger())
1960 Found = true;
1961 }
1962
1963 if (SawPoison)
1964 Res.push_back(x: AnyValue::poison());
1965 else
1966 Res.push_back(x: AnyValue::boolean(Val: Found));
1967 }
1968
1969 return std::move(Res);
1970 }
1971 case Intrinsic::experimental_vector_histogram_add:
1972 case Intrinsic::experimental_vector_histogram_uadd_sat:
1973 case Intrinsic::experimental_vector_histogram_umax:
1974 case Intrinsic::experimental_vector_histogram_umin:
1975 return callExperimentalVectorHistogramIntrinsic(CB, Args, IID);
1976 default:
1977 Handler.onUnrecognizedInstruction(I&: CB);
1978 setFailed();
1979 return AnyValue();
1980 }
1981 }
1982
1983 AnyValue callLibFunc(CallBase &CB, Function *ResolvedCallee,
1984 ArrayRef<AnyValue> CalleeArgs) {
1985 LibFunc LF = CurrentFrame->TLI.getLibFunc(FDecl: *ResolvedCallee);
1986 // Respect nobuiltin attributes on call site.
1987 if (CB.isNoBuiltin() || LF == NotLibFunc) {
1988 Handler.onUnrecognizedInstruction(I&: CB);
1989 setFailed();
1990 return AnyValue();
1991 }
1992
1993 if (auto LibCallRes = Lib.executeLibcall(LF, Name: CB.getName(),
1994 FuncType: CB.getFunctionType(), Args: CalleeArgs))
1995 return *LibCallRes;
1996
1997 if (ExitInfo)
1998 return AnyValue();
1999
2000 Handler.onUnrecognizedInstruction(I&: CB);
2001 setFailed();
2002 return AnyValue();
2003 }
2004
2005 /// Handle both poison-generating and UB-implying attributes for parameters
2006 /// and return values.
2007 void handleAttributes(Type *Ty, AnyValue &V, AttributeSet AttrsAtCallSite,
2008 AttributeSet AttrsAtCallee) {
2009 if (Ty->isIntOrIntVectorTy()) {
2010 if (auto CRAttr = AttrsAtCallSite.getAttribute(Kind: Attribute::Range);
2011 CRAttr.isValid())
2012 applyRangeAttr(V, CR: CRAttr.getRange());
2013 if (auto CRAttr = AttrsAtCallee.getAttribute(Kind: Attribute::Range);
2014 CRAttr.isValid())
2015 applyRangeAttr(V, CR: CRAttr.getRange());
2016 }
2017 if (AttributeFuncs::isNoFPClassCompatibleType(Ty)) {
2018 if (auto CRAttr = AttrsAtCallSite.getAttribute(Kind: Attribute::NoFPClass);
2019 CRAttr.isValid())
2020 applyNoFPClassAttr(V, NoFPClass: CRAttr.getNoFPClass());
2021 if (auto CRAttr = AttrsAtCallee.getAttribute(Kind: Attribute::NoFPClass);
2022 CRAttr.isValid())
2023 applyNoFPClassAttr(V, NoFPClass: CRAttr.getNoFPClass());
2024 }
2025 if (Ty->isPointerTy()) {
2026 if (AttrsAtCallSite.hasAttribute(Kind: Attribute::NonNull) ||
2027 AttrsAtCallee.hasAttribute(Kind: Attribute::NonNull))
2028 applyNonNullAttr(V, AS: Ty->getPointerAddressSpace(), DL);
2029 }
2030 if (Ty->isPtrOrPtrVectorTy()) {
2031 if (MaybeAlign Align = AttrsAtCallSite.getAlignment())
2032 applyAlignAttr(V, Alignment: *Align);
2033 if (MaybeAlign Align = AttrsAtCallee.getAlignment())
2034 applyAlignAttr(V, Alignment: *Align);
2035 }
2036 if ((AttrsAtCallSite.hasAttribute(Kind: Attribute::NoUndef) ||
2037 AttrsAtCallee.hasAttribute(Kind: Attribute::NoUndef)) &&
2038 violatesNoUndefAttr(V)) {
2039 reportImmediateUB() << "The value " << V
2040 << " violates noundef attribute.";
2041 return;
2042 }
2043 if (Ty->isPointerTy()) {
2044 unsigned AS = Ty->getPointerAddressSpace();
2045 if (uint64_t DereferenceableBytes =
2046 std::max(a: AttrsAtCallSite.getDereferenceableBytes(),
2047 b: AttrsAtCallee.getDereferenceableBytes())) {
2048 if (violatesDereferenceableBytesAttr(V, Bytes: DereferenceableBytes,
2049 /*OrNull=*/false, AS, Ctx))
2050 reportImmediateUB()
2051 << "The value " << V << " violates dereferenceable("
2052 << DereferenceableBytes << ") attribute.";
2053 } else if (uint64_t DereferenceableOrNullBytes =
2054 std::max(a: AttrsAtCallSite.getDereferenceableOrNullBytes(),
2055 b: AttrsAtCallee.getDereferenceableOrNullBytes())) {
2056 if (violatesDereferenceableBytesAttr(V, Bytes: DereferenceableOrNullBytes,
2057 /*OrNull=*/true, AS, Ctx))
2058 reportImmediateUB() << "The value " << V
2059 << " violates "
2060 "dereferenceable_or_null("
2061 << DereferenceableOrNullBytes << ") attribute.";
2062 }
2063 }
2064 }
2065
2066 /// Handle both poison-generating and UB-implying metadata on instructions.
2067 void handleMetadata(Type *Ty, AnyValue &V, Instruction &I) {
2068 auto ExtractFirstIntOperand = [](const MDNode *Node) {
2069 return mdconst::extract<ConstantInt>(MD: Node->getOperand(I: 0))->getZExtValue();
2070 };
2071
2072 if (Ty->isIntOrIntVectorTy()) {
2073 if (MDNode *Ranges = I.getMetadata(KindID: LLVMContext::MD_range)) {
2074 SmallVector<ConstantRange> RangeList;
2075 for (uint32_t I = 0; I < Ranges->getNumOperands(); I += 2) {
2076 RangeList.emplace_back(
2077 Args: mdconst::extract<ConstantInt>(MD: Ranges->getOperand(I))->getValue(),
2078 Args: mdconst::extract<ConstantInt>(MD: Ranges->getOperand(I: I + 1))
2079 ->getValue());
2080 }
2081 forEachScalarValue(V, Visit: [&](AnyValue &Scalar) {
2082 if (!Scalar.isInteger())
2083 return;
2084 for (auto &CR : RangeList)
2085 if (CR.contains(Val: Scalar.asInteger()))
2086 return;
2087 Scalar = AnyValue::poison();
2088 });
2089 }
2090 }
2091 if (AttributeFuncs::isNoFPClassCompatibleType(Ty)) {
2092 if (const MDNode *NoFPClass = I.getMetadata(KindID: LLVMContext::MD_nofpclass)) {
2093 applyNoFPClassAttr(
2094 V, NoFPClass: static_cast<FPClassTest>(ExtractFirstIntOperand(NoFPClass)));
2095 }
2096 }
2097 if (Ty->isPointerTy()) {
2098 if (I.hasMetadata(KindID: LLVMContext::MD_nonnull))
2099 applyNonNullAttr(V, AS: Ty->getPointerAddressSpace(), DL);
2100 // Unlike align attributes, !align is only defined for pointer types.
2101 if (const MDNode *Alignment = I.getMetadata(KindID: LLVMContext::MD_align))
2102 applyAlignAttr(V, Alignment: Align(ExtractFirstIntOperand(Alignment)));
2103 }
2104 if (I.hasMetadata(KindID: LLVMContext::MD_noundef) && violatesNoUndefAttr(V)) {
2105 reportImmediateUB() << "The value " << V
2106 << " violates !noundef metadata.";
2107 return;
2108 }
2109 if (Ty->isPointerTy()) {
2110 unsigned AS = Ty->getPointerAddressSpace();
2111 if (const MDNode *DereferenceableBytes =
2112 I.getMetadata(KindID: LLVMContext::MD_dereferenceable)) {
2113 uint64_t Bytes = ExtractFirstIntOperand(DereferenceableBytes);
2114 if (violatesDereferenceableBytesAttr(V, Bytes,
2115 /*OrNull=*/false, AS, Ctx))
2116 reportImmediateUB()
2117 << "The value " << V << " violates !dereferenceable !{i64 "
2118 << Bytes << "} metadata.";
2119 } else if (const MDNode *DereferenceableOrNullBytes =
2120 I.getMetadata(KindID: LLVMContext::MD_dereferenceable_or_null)) {
2121 uint64_t Bytes = ExtractFirstIntOperand(DereferenceableOrNullBytes);
2122 if (violatesDereferenceableBytesAttr(V, Bytes,
2123 /*OrNull=*/true, AS, Ctx))
2124 reportImmediateUB()
2125 << "The value " << V << " violates !dereferenceable_or_null!{i64 "
2126 << Bytes << "} metadata.";
2127 }
2128 }
2129 }
2130
2131 void enterCall(CallBase &CB) {
2132 Function *Callee = CB.getCalledFunction();
2133 // TODO: handle initializes
2134 auto &CalleeArgs = CurrentFrame->CalleeArgs;
2135 assert(CalleeArgs.empty() &&
2136 "Forgot to call returnFromCallee before entering a new call.");
2137 for (Value *Arg : CB.args())
2138 CalleeArgs.push_back(Elt: getValue(V: Arg));
2139
2140 if (!Callee) {
2141 Value *CalledOperand = CB.getCalledOperand();
2142 if (isNoopInlineAsm(V: CalledOperand, RetTy: CB.getType())) {
2143 CurrentFrame->ResolvedCallee = nullptr;
2144 returnFromCallee();
2145 return;
2146 }
2147
2148 if (isa<InlineAsm>(Val: CalledOperand)) {
2149 Handler.onUnrecognizedInstruction(I&: CB);
2150 setFailed();
2151 return;
2152 }
2153
2154 auto &CalleeVal = getValue(V: CalledOperand);
2155 if (CalleeVal.isPoison()) {
2156 reportImmediateUB() << "Indirect call through poison function pointer.";
2157 return;
2158 }
2159 Callee = Ctx.getTargetFunction(Ptr: CalleeVal.asPointer());
2160 if (!Callee) {
2161 reportImmediateUB()
2162 << "Indirect call through invalid function pointer.";
2163 return;
2164 }
2165 if (Callee->getFunctionType() != CB.getFunctionType()) {
2166 reportImmediateUB() << "Indirect call through a function pointer with "
2167 "mismatched signature. Expected: "
2168 << *CB.getFunctionType()
2169 << ", Actual: " << *Callee->getFunctionType();
2170 return;
2171 }
2172 }
2173
2174 assert(Callee && "Expected a resolved callee function.");
2175 assert(
2176 Callee->getFunctionType() == CB.getFunctionType() &&
2177 "Expected the callee function type to match the call site signature.");
2178
2179 // Handle parameter attributes (Attributes from resolved callee should be
2180 // applied if available).
2181 for (auto [I, Arg] : enumerate(First: CB.args())) {
2182 Type *ArgTy = Arg->getType();
2183 AnyValue &ArgVal = CalleeArgs[I];
2184
2185 // CallBase::paramHasAttr also checks parameter attributes at known
2186 // callee. We do it explicitly to avoid duplication.
2187 AttributeSet AttrsAtCallSite = CB.getParamAttributes(ArgNo: I);
2188 AttributeSet AttrsAtCallee = Callee->getAttributes().getParamAttrs(ArgNo: I);
2189
2190 if (ArgTy->isPointerTy()) {
2191 auto *ByValTy = AttrsAtCallSite.getByValType();
2192 auto *ByValTyFromCallee = AttrsAtCallee.getByValType();
2193 if (ByValTy != ByValTyFromCallee) {
2194 reportImmediateUB()
2195 << "Mismatched byval attribute between callee and callsite.";
2196 return;
2197 }
2198 if (ByValTy) {
2199 if (ArgVal.isPoison()) {
2200 reportImmediateUB() << "Invalid poison byval pointer argument.";
2201 return;
2202 }
2203
2204 uint64_t Size = Ctx.getEffectiveTypeAllocSize(Ty: ByValTy);
2205 MaybeAlign AllocAlign = AttrsAtCallSite.getAlignment();
2206 // Ignore the alignment at the callsite when it is set on the callee.
2207 if (MaybeAlign CalleeAlign = AttrsAtCallee.getAlignment())
2208 AllocAlign = CalleeAlign;
2209 if (!AllocAlign.has_value()) {
2210 // If the alignment is not specified, we use the default ABI
2211 // alignment. This is the default behavior of
2212 // TargetLoweringBase::getByValTypeAlignment.
2213 AllocAlign = DL.getABITypeAlign(Ty: ByValTy);
2214 }
2215 assert(I < Callee->arg_size() &&
2216 "Byval pointers cannot be passed via variadic arguments.");
2217 auto Obj = Ctx.allocate(
2218 Size, Align: AllocAlign->value(), Name: Callee->getArg(i: I)->getName(),
2219 AS: ArgTy->getPointerAddressSpace(), InitKind: MemInitKind::Uninitialized,
2220 AllocKind: MemAllocKind::Stack);
2221 if (!Obj) {
2222 reportError()
2223 << "Insufficient stack space for byval pointer argument.";
2224 return;
2225 }
2226 if (auto [MO, Offset] = verifyMemAccess(
2227 Ptr: ArgVal.asPointer(), AccessSize: Size,
2228 Alignment: std::max(a: AllocAlign.value(),
2229 b: AttrsAtCallSite.getAlignment().valueOrOne()),
2230 /*IsStore=*/false);
2231 MO)
2232 copy(Range: MO->getBytes().slice(N: Offset, M: Size), Out: Obj->getBytes().begin());
2233 else
2234 return;
2235 CurrentFrame->CalleeByValArgs.push_back(Elt: Obj);
2236 ArgVal = Ctx.deriveFromMemoryObject(Obj: std::move(Obj));
2237 }
2238 }
2239 handleAttributes(Ty: ArgTy, V&: ArgVal, AttrsAtCallSite, AttrsAtCallee);
2240 }
2241
2242 CurrentFrame->ResolvedCallee = Callee;
2243 ArrayRef<AnyValue> Args = CalleeArgs;
2244 if (Function *Oracle = getSpeculativeLoadOracle(CB)) {
2245 Args = Args.drop_front(N: 3);
2246 for (auto [Arg, ArgVal] :
2247 zip_equal(t: Oracle->args(), u: MutableArrayRef(CalleeArgs).drop_front(N: 3)))
2248 handleAttributes(Ty: Arg.getType(), V&: ArgVal, AttrsAtCallSite: AttributeSet(),
2249 AttrsAtCallee: Arg.getAttributes());
2250 Callee = Oracle;
2251 }
2252 if (Callee->isIntrinsic()) {
2253 CurrentFrame->CalleeRetVal = callIntrinsic(CB, Args: CalleeArgs);
2254 returnFromCallee();
2255 return;
2256 } else if (Callee->isDeclaration()) {
2257 CurrentFrame->CalleeRetVal = callLibFunc(CB, ResolvedCallee: Callee, CalleeArgs);
2258 returnFromCallee();
2259 return;
2260 } else {
2261 uint32_t MaxStackDepth = Ctx.getMaxStackDepth();
2262 if (MaxStackDepth && CallStack.size() >= MaxStackDepth) {
2263 reportError() << "Maximum stack depth exceeded.";
2264 return;
2265 }
2266 assert(!Callee->empty() && "Expected a defined function.");
2267 // Suspend the current frame and push the callee frame onto the stack.
2268 AnyValue &RetVal = CurrentFrame->CalleeRetVal;
2269 CurrentFrame->State = FrameState::Pending;
2270 CallStack.emplace_back(args&: *Callee, args: &CB, args&: CurrentFrame, args&: Args, args&: RetVal,
2271 args: Ctx.getTLIImpl());
2272 }
2273 }
2274
2275 void visitCallInst(CallInst &CI) { enterCall(CB&: CI); }
2276
2277 void visitInvokeInst(InvokeInst &II) {
2278 // TODO: handle exceptions
2279 enterCall(CB&: II);
2280 }
2281
2282 void visitAdd(BinaryOperator &I) {
2283 visitIntBinOp(I, ScalarFn: [&](const APInt &LHS, const APInt &RHS) {
2284 return addNoWrap(LHS, RHS, HasNSW: I.hasNoSignedWrap(), HasNUW: I.hasNoUnsignedWrap());
2285 });
2286 }
2287
2288 void visitSub(BinaryOperator &I) {
2289 visitIntBinOp(I, ScalarFn: [&](const APInt &LHS, const APInt &RHS) {
2290 return subNoWrap(LHS, RHS, HasNSW: I.hasNoSignedWrap(), HasNUW: I.hasNoUnsignedWrap());
2291 });
2292 }
2293
2294 void visitMul(BinaryOperator &I) {
2295 visitIntBinOp(I, ScalarFn: [&](const APInt &LHS, const APInt &RHS) {
2296 return mulNoWrap(LHS, RHS, HasNSW: I.hasNoSignedWrap(), HasNUW: I.hasNoUnsignedWrap());
2297 });
2298 }
2299
2300 void visitSDiv(BinaryOperator &I) {
2301 visitBinOp(I, ScalarFn: [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
2302 // Priority: Immediate UB > poison > normal value
2303 if (RHS.isPoison()) {
2304 reportImmediateUB() << "Division by zero (refine RHS to 0).";
2305 return AnyValue::poison();
2306 }
2307 const APInt &RHSVal = RHS.asInteger();
2308 if (RHSVal.isZero()) {
2309 reportImmediateUB() << "Division by zero.";
2310 return AnyValue::poison();
2311 }
2312 if (LHS.isPoison()) {
2313 if (RHSVal.isAllOnes())
2314 reportImmediateUB()
2315 << "Signed division overflow (refine LHS to INT_MIN).";
2316 return AnyValue::poison();
2317 }
2318 const APInt &LHSVal = LHS.asInteger();
2319 if (LHSVal.isMinSignedValue() && RHSVal.isAllOnes()) {
2320 reportImmediateUB() << "Signed division overflow.";
2321 return AnyValue::poison();
2322 }
2323
2324 if (I.isExact()) {
2325 APInt Q, R;
2326 APInt::sdivrem(LHS: LHSVal, RHS: RHSVal, Quotient&: Q, Remainder&: R);
2327 if (!R.isZero())
2328 return AnyValue::poison();
2329 return Q;
2330 } else {
2331 return LHSVal.sdiv(RHS: RHSVal);
2332 }
2333 });
2334 }
2335
2336 void visitSRem(BinaryOperator &I) {
2337 visitBinOp(I, ScalarFn: [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
2338 // Priority: Immediate UB > poison > normal value
2339 if (RHS.isPoison()) {
2340 reportImmediateUB() << "Division by zero (refine RHS to 0).";
2341 return AnyValue::poison();
2342 }
2343 const APInt &RHSVal = RHS.asInteger();
2344 if (RHSVal.isZero()) {
2345 reportImmediateUB() << "Division by zero.";
2346 return AnyValue::poison();
2347 }
2348 if (LHS.isPoison()) {
2349 if (RHSVal.isAllOnes())
2350 reportImmediateUB()
2351 << "Signed division overflow (refine LHS to INT_MIN).";
2352 return AnyValue::poison();
2353 }
2354 const APInt &LHSVal = LHS.asInteger();
2355 if (LHSVal.isMinSignedValue() && RHSVal.isAllOnes()) {
2356 reportImmediateUB() << "Signed division overflow. LHS: " << LHSVal
2357 << ", RHS: " << RHSVal;
2358 return AnyValue::poison();
2359 }
2360
2361 return LHSVal.srem(RHS: RHSVal);
2362 });
2363 }
2364
2365 void visitUDiv(BinaryOperator &I) {
2366 visitBinOp(I, ScalarFn: [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
2367 // Priority: Immediate UB > poison > normal value
2368 if (RHS.isPoison()) {
2369 reportImmediateUB() << "Division by zero (refine RHS to 0).";
2370 return AnyValue::poison();
2371 }
2372 const APInt &RHSVal = RHS.asInteger();
2373 if (RHSVal.isZero()) {
2374 reportImmediateUB() << "Division by zero.";
2375 return AnyValue::poison();
2376 }
2377 if (LHS.isPoison())
2378 return AnyValue::poison();
2379 const APInt &LHSVal = LHS.asInteger();
2380
2381 if (I.isExact()) {
2382 APInt Q, R;
2383 APInt::udivrem(LHS: LHSVal, RHS: RHSVal, Quotient&: Q, Remainder&: R);
2384 if (!R.isZero())
2385 return AnyValue::poison();
2386 return Q;
2387 } else {
2388 return LHSVal.udiv(RHS: RHSVal);
2389 }
2390 });
2391 }
2392
2393 void visitURem(BinaryOperator &I) {
2394 visitBinOp(I, ScalarFn: [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
2395 // Priority: Immediate UB > poison > normal value
2396 if (RHS.isPoison()) {
2397 reportImmediateUB() << "Division by zero (refine RHS to 0).";
2398 return AnyValue::poison();
2399 }
2400 const APInt &RHSVal = RHS.asInteger();
2401 if (RHSVal.isZero()) {
2402 reportImmediateUB() << "Division by zero.";
2403 return AnyValue::poison();
2404 }
2405 if (LHS.isPoison())
2406 return AnyValue::poison();
2407 const APInt &LHSVal = LHS.asInteger();
2408 return LHSVal.urem(RHS: RHSVal);
2409 });
2410 }
2411
2412 void visitFAdd(BinaryOperator &I) {
2413 visitFPBinOp(I, ScalarFn: [](const APFloat &LHS, const APFloat &RHS) -> APFloat {
2414 APFloat Res = LHS;
2415 Res.add(RHS, RM: APFloat::rmNearestTiesToEven);
2416 return Res;
2417 });
2418 }
2419
2420 void visitFSub(BinaryOperator &I) {
2421 visitFPBinOp(I, ScalarFn: [](const APFloat &LHS, const APFloat &RHS) -> APFloat {
2422 APFloat Res = LHS;
2423 Res.subtract(RHS, RM: APFloat::rmNearestTiesToEven);
2424 return Res;
2425 });
2426 }
2427
2428 void visitFMul(BinaryOperator &I) {
2429 visitFPBinOp(I, ScalarFn: [](const APFloat &LHS, const APFloat &RHS) -> APFloat {
2430 APFloat Res = LHS;
2431 Res.multiply(RHS, RM: APFloat::rmNearestTiesToEven);
2432 return Res;
2433 });
2434 }
2435
2436 void visitFDiv(BinaryOperator &I) {
2437 visitFPBinOp(I, ScalarFn: [](const APFloat &LHS, const APFloat &RHS) -> APFloat {
2438 APFloat Res = LHS;
2439 Res.divide(RHS, RM: APFloat::rmNearestTiesToEven);
2440 return Res;
2441 });
2442 }
2443
2444 void visitFRem(BinaryOperator &I) {
2445 visitFPBinOp(I, ScalarFn: [](const APFloat &LHS, const APFloat &RHS) -> APFloat {
2446 APFloat Res = LHS;
2447 Res.mod(RHS);
2448 return Res;
2449 });
2450 }
2451
2452 void visitFNeg(UnaryOperator &I) {
2453 visitBitwiseFPUnOp(
2454 I, ScalarFn: [](const APFloat &Operand) -> APFloat { return -Operand; });
2455 }
2456
2457 void visitTruncInst(TruncInst &Trunc) {
2458 visitIntUnOp(I&: Trunc, ScalarFn: [&](const APInt &Operand) -> AnyValue {
2459 unsigned DestBW = Trunc.getType()->getScalarSizeInBits();
2460 if (Trunc.hasNoSignedWrap() && Operand.getSignificantBits() > DestBW)
2461 return AnyValue::poison();
2462 if (Trunc.hasNoUnsignedWrap() && Operand.getActiveBits() > DestBW)
2463 return AnyValue::poison();
2464 return Operand.trunc(width: DestBW);
2465 });
2466 }
2467
2468 void visitZExtInst(ZExtInst &ZExt) {
2469 visitIntUnOp(I&: ZExt, ScalarFn: [&](const APInt &Operand) -> AnyValue {
2470 uint32_t DestBW = ZExt.getDestTy()->getScalarSizeInBits();
2471 if (ZExt.hasNonNeg() && Operand.isNegative())
2472 return AnyValue::poison();
2473 return Operand.zext(width: DestBW);
2474 });
2475 }
2476
2477 void visitSExtInst(SExtInst &SExt) {
2478 visitIntUnOp(I&: SExt, ScalarFn: [&](const APInt &Operand) -> AnyValue {
2479 uint32_t DestBW = SExt.getDestTy()->getScalarSizeInBits();
2480 return Operand.sext(width: DestBW);
2481 });
2482 }
2483
2484 void visitFPExtInst(FPExtInst &FPExt) { visitFPConvInst(I&: FPExt); }
2485
2486 void visitFPTruncInst(FPTruncInst &FPTrunc) { visitFPConvInst(I&: FPTrunc); }
2487
2488 void visitFPConvInst(Instruction &I) {
2489 if (!Ctx.isDefaultFPEnv())
2490 reportImmediateUB() << "Non-constrained floating-point operation assumes "
2491 "default floating-point environment";
2492
2493 const fltSemantics &DstSem =
2494 I.getType()->getScalarType()->getFltSemantics();
2495
2496 visitUnOp(I, ScalarFn: [&](const AnyValue &Operand) -> AnyValue {
2497 if (Operand.isPoison())
2498 return AnyValue::poison();
2499
2500 FastMathFlags FMF = cast<FPMathOperator>(Val&: I).getFastMathFlags();
2501 DenormalMode DenormMode =
2502 getCurrentDenormalMode(Ty: I.getOperand(i: 0)->getType());
2503
2504 auto ValidatedOperand = handleFMFFlags(Val: Operand, FMF, /*IsInput=*/true);
2505 if (ValidatedOperand.isPoison())
2506 return ValidatedOperand;
2507
2508 APFloat FOperand = handleDenormal(Val: ValidatedOperand.asFloat(),
2509 Mode: DenormMode.Input, /*IsInput=*/true);
2510 APFloat SourceNaN = FOperand;
2511
2512 bool LosesInfo;
2513 FOperand.convert(ToSemantics: DstSem, RM: Ctx.getCurrentRoundingMode(), losesInfo: &LosesInfo);
2514
2515 if (auto ValidateRes = handleFMFFlags(Val: FOperand, FMF, /*IsInput=*/false);
2516 ValidateRes.isPoison())
2517 return ValidateRes;
2518
2519 FOperand = handleDenormal(Val: std::move(FOperand), Mode: DenormMode.Output, IsInput: true);
2520
2521 return AnyValue(applyNaNPropagation(Result: FOperand, Inputs: {&SourceNaN}));
2522 });
2523 }
2524
2525 void visitFPToSIInst(FPToSIInst &FPToSI) {
2526 visitFPToIntInst(I&: FPToSI, /*IsUnsigned=*/false);
2527 }
2528
2529 void visitFPToUIInst(FPToUIInst &FPToUI) {
2530 visitFPToIntInst(I&: FPToUI, /*IsUnsigned=*/true);
2531 }
2532
2533 void visitFPToIntInst(Instruction &I, bool IsUnsigned) {
2534 // Note: We DO NOT use CurrentRoundingMode here.
2535 // Language specs require truncation towards zero for FP-to-Int conversions.
2536 visitUnOp(I, ScalarFn: [&](const AnyValue &Operand) -> AnyValue {
2537 if (Operand.isPoison())
2538 return AnyValue::poison();
2539
2540 APSInt Res(I.getType()->getScalarSizeInBits(), /*isUnsigned=*/IsUnsigned);
2541 bool IsExact;
2542 APFloat::opStatus Status = Operand.asFloat().convertToInteger(
2543 Result&: Res, RM: APFloat::rmTowardZero, IsExact: &IsExact);
2544
2545 if (Status == APFloat::opInvalidOp)
2546 return AnyValue::poison();
2547
2548 return AnyValue(Res);
2549 });
2550 }
2551
2552 void visitSIToFPInst(SIToFPInst &SIToFP) {
2553 visitIntToFPInst(I&: SIToFP, /*IsSigned=*/true);
2554 }
2555
2556 void visitUIToFPInst(UIToFPInst &UIToFP) {
2557 visitIntToFPInst(I&: UIToFP, /*IsSigned=*/false);
2558 }
2559
2560 void visitIntToFPInst(Instruction &I, bool IsSigned) {
2561 const fltSemantics &DstSem =
2562 I.getType()->getScalarType()->getFltSemantics();
2563 FastMathFlags FMF = cast<FPMathOperator>(Val&: I).getFastMathFlags();
2564
2565 visitUnOp(I, ScalarFn: [&](const AnyValue &Operand) -> AnyValue {
2566 if (Operand.isPoison())
2567 return AnyValue::poison();
2568
2569 APInt IOperand = Operand.asInteger();
2570
2571 if (isa<UIToFPInst>(Val: I) && I.hasNonNeg() && IOperand.isNegative())
2572 return AnyValue::poison();
2573
2574 APFloat Res(DstSem);
2575
2576 Res.convertFromAPInt(Input: Operand.asInteger(), /*IsSigned=*/IsSigned,
2577 RM: Ctx.getCurrentRoundingMode());
2578
2579 // We need IsInput=true here because the nsz flag applies to the output.
2580 return handleFMFFlags(Val: Res, FMF, /*IsInput=*/true);
2581 });
2582 }
2583
2584 void visitAnd(BinaryOperator &I) {
2585 visitIntBinOp(I, ScalarFn: [](const APInt &LHS, const APInt &RHS) -> AnyValue {
2586 return LHS & RHS;
2587 });
2588 }
2589
2590 void visitXor(BinaryOperator &I) {
2591 visitIntBinOp(I, ScalarFn: [](const APInt &LHS, const APInt &RHS) -> AnyValue {
2592 return LHS ^ RHS;
2593 });
2594 }
2595
2596 void visitOr(BinaryOperator &I) {
2597 visitIntBinOp(I, ScalarFn: [&](const APInt &LHS, const APInt &RHS) -> AnyValue {
2598 if (cast<PossiblyDisjointInst>(Val&: I).isDisjoint() && LHS.intersects(RHS))
2599 return AnyValue::poison();
2600 return LHS | RHS;
2601 });
2602 }
2603
2604 void visitShl(BinaryOperator &I) {
2605 visitIntBinOp(I, ScalarFn: [&](const APInt &LHS, const APInt &RHS) -> AnyValue {
2606 if (RHS.uge(RHS: LHS.getBitWidth()))
2607 return AnyValue::poison();
2608 if (I.hasNoSignedWrap() && RHS.uge(RHS: LHS.getNumSignBits()))
2609 return AnyValue::poison();
2610 if (I.hasNoUnsignedWrap() && RHS.ugt(RHS: LHS.countl_zero()))
2611 return AnyValue::poison();
2612 return LHS.shl(ShiftAmt: RHS);
2613 });
2614 }
2615
2616 void visitLShr(BinaryOperator &I) {
2617 visitIntBinOp(I, ScalarFn: [&](const APInt &LHS, const APInt &RHS) -> AnyValue {
2618 if (RHS.uge(RHS: LHS.getBitWidth()) ||
2619 (cast<PossiblyExactOperator>(Val&: I).isExact() &&
2620 RHS.ugt(RHS: LHS.countr_zero())))
2621 return AnyValue::poison();
2622 return LHS.lshr(ShiftAmt: RHS);
2623 });
2624 }
2625
2626 void visitAShr(BinaryOperator &I) {
2627 visitIntBinOp(I, ScalarFn: [&](const APInt &LHS, const APInt &RHS) -> AnyValue {
2628 if (RHS.uge(RHS: LHS.getBitWidth()) ||
2629 (cast<PossiblyExactOperator>(Val&: I).isExact() &&
2630 RHS.ugt(RHS: LHS.countr_zero())))
2631 return AnyValue::poison();
2632 return LHS.ashr(ShiftAmt: RHS);
2633 });
2634 }
2635
2636 void visitICmpInst(ICmpInst &I) {
2637 visitBinOp(I, ScalarFn: [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
2638 if (LHS.isPoison() || RHS.isPoison())
2639 return AnyValue::poison();
2640 const APInt &LHSVal =
2641 LHS.isPointer() ? LHS.asPointer().address() : LHS.asInteger();
2642 const APInt &RHSVal =
2643 RHS.isPointer() ? RHS.asPointer().address() : RHS.asInteger();
2644 if (I.hasSameSign() && LHSVal.isNonNegative() != RHSVal.isNonNegative())
2645 return AnyValue::poison();
2646 return AnyValue::boolean(
2647 Val: ICmpInst::compare(LHS: LHSVal, RHS: RHSVal, Pred: I.getPredicate()));
2648 });
2649 }
2650
2651 void visitFCmpInst(FCmpInst &I) {
2652 DenormalMode DenormMode =
2653 getCurrentDenormalMode(Ty: I.getOperand(i_nocapture: 0)->getType());
2654 FastMathFlags FMF = I.getFastMathFlags();
2655
2656 visitBinOp(I, ScalarFn: [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
2657 if (LHS.isPoison() || RHS.isPoison())
2658 return AnyValue::poison();
2659
2660 if (auto ValidateRes = handleFMFFlags(Val: LHS, FMF, /*IsInput=*/true);
2661 ValidateRes.isPoison())
2662 return ValidateRes;
2663 if (auto ValidateRes = handleFMFFlags(Val: RHS, FMF, /*IsInput=*/true);
2664 ValidateRes.isPoison())
2665 return ValidateRes;
2666
2667 APFloat FLHS =
2668 handleDenormal(Val: LHS.asFloat(), Mode: DenormMode.Input, /*IsInput=*/true);
2669 APFloat FRHS =
2670 handleDenormal(Val: RHS.asFloat(), Mode: DenormMode.Input, /*IsInput=*/true);
2671
2672 return AnyValue::boolean(Val: FCmpInst::compare(LHS: FLHS, RHS: FRHS, Pred: I.getPredicate()));
2673 });
2674 }
2675
2676 void visitSelect(SelectInst &SI) {
2677 AnyValue Res;
2678
2679 if (SI.getCondition()->getType()->isIntegerTy(BitWidth: 1)) {
2680 switch (getValue(V: SI.getCondition()).asBoolean()) {
2681 case BooleanKind::True:
2682 Res = getValue(V: SI.getTrueValue());
2683 break;
2684 case BooleanKind::False:
2685 Res = getValue(V: SI.getFalseValue());
2686 break;
2687 case BooleanKind::Poison:
2688 Res = AnyValue::getPoisonValue(Ctx, Ty: SI.getType());
2689 break;
2690 }
2691 } else {
2692 auto &Cond = getValue(V: SI.getCondition()).asAggregate();
2693 auto &TV = getValue(V: SI.getTrueValue()).asAggregate();
2694 auto &FV = getValue(V: SI.getFalseValue()).asAggregate();
2695 std::vector<AnyValue> ResVec;
2696 size_t Len = Cond.size();
2697 ResVec.reserve(n: Len);
2698 for (uint32_t I = 0; I != Len; ++I) {
2699 switch (Cond[I].asBoolean()) {
2700 case BooleanKind::True:
2701 ResVec.push_back(x: TV[I]);
2702 break;
2703 case BooleanKind::False:
2704 ResVec.push_back(x: FV[I]);
2705 break;
2706 case BooleanKind::Poison:
2707 ResVec.push_back(
2708 x: AnyValue::getPoisonValue(Ctx, Ty: SI.getType()->getScalarType()));
2709 break;
2710 }
2711 }
2712 Res = AnyValue(std::move(ResVec));
2713 }
2714
2715 // Handle fast-math flags
2716 if (auto *FPMO = dyn_cast<FPMathOperator>(Val: &SI)) {
2717 if (FastMathFlags FMF = FPMO->getFastMathFlags(); FMF.any())
2718 Res = handleFMFFlags(Val: std::move(Res), FMF, /*IsInput=*/true);
2719 }
2720
2721 setResult(I&: SI, V: std::move(Res));
2722 }
2723
2724 void visitAllocaInst(AllocaInst &AI) {
2725 uint64_t AllocSize = Ctx.getEffectiveTypeSize(Size: AI.getAllocationBaseSize(DL));
2726 if (AI.isArrayAllocation()) {
2727 auto &Size = getValue(V: AI.getArraySize());
2728 if (Size.isPoison()) {
2729 reportImmediateUB() << "Alloca with poison array size.";
2730 return;
2731 }
2732 if (Size.asInteger().getActiveBits() > 64) {
2733 reportImmediateUB()
2734 << "Alloca with large array size that overflows uint64_t. Size: "
2735 << Size.asInteger();
2736 return;
2737 }
2738 bool Overflowed = false;
2739 AllocSize = SaturatingMultiply(X: AllocSize, Y: Size.asInteger().getZExtValue(),
2740 ResultOverflowed: &Overflowed);
2741 if (Overflowed) {
2742 reportImmediateUB()
2743 << "Alloca with allocation size that overflows uint64_t. Size: "
2744 << Size.asInteger();
2745 return;
2746 }
2747 }
2748 // If it is used by llvm.lifetime.start, it should be initially dead.
2749 bool IsInitiallyDead = any_of(Range: AI.users(), P: [](User *U) {
2750 return match(V: U, P: m_Intrinsic<Intrinsic::lifetime_start>());
2751 });
2752 auto Obj = Ctx.allocate(Size: AllocSize, Align: AI.getPointerAlignment(DL).value(),
2753 Name: AI.getName(), AS: AI.getAddressSpace(),
2754 InitKind: IsInitiallyDead ? MemInitKind::Poisoned
2755 : MemInitKind::Uninitialized,
2756 AllocKind: MemAllocKind::Stack);
2757 if (!Obj) {
2758 reportError() << "Insufficient stack space.";
2759 return;
2760 }
2761 CurrentFrame->Allocas.push_back(Elt: Obj);
2762 setResult(I&: AI, V: Ctx.deriveFromMemoryObject(Obj));
2763 }
2764
2765 void visitGetElementPtrInst(GetElementPtrInst &GEP) {
2766 setResult(I&: GEP, V: Ctx.computeGEP(GEP&: cast<GEPOperator>(Val&: GEP),
2767 GetValue: [this](Value *V) -> const AnyValue & {
2768 return getValue(V);
2769 }));
2770 }
2771
2772 void visitPtrToInt(PtrToIntInst &I) {
2773 unsigned BitWidth = I.getType()->getScalarSizeInBits();
2774 return visitUnOp(I, ScalarFn: [this, BitWidth](const AnyValue &V) -> AnyValue {
2775 if (V.isPoison())
2776 return AnyValue::poison();
2777 Ctx.exposeProvenance(Prov&: V.asPointer().provenance());
2778 return V.asPointer().address().zextOrTrunc(width: BitWidth);
2779 });
2780 }
2781
2782 void visitIntToPtr(IntToPtrInst &I) {
2783 return visitUnOp(I, ScalarFn: [&](const AnyValue &V) -> AnyValue {
2784 if (V.isPoison())
2785 return AnyValue::poison();
2786 auto Prov = Ctx.getWildcardProvenance();
2787 // TODO: check metadata
2788 return Pointer(std::move(Prov),
2789 V.asInteger().zextOrTrunc(width: DL.getPointerSizeInBits(
2790 AS: I.getType()->getPointerAddressSpace())));
2791 });
2792 }
2793
2794 void visitPtrToAddr(PtrToAddrInst &I) {
2795 unsigned BitWidth = I.getType()->getScalarSizeInBits();
2796 return visitUnOp(I, ScalarFn: [&](const AnyValue &V) -> AnyValue {
2797 if (V.isPoison())
2798 return AnyValue::poison();
2799 return V.asPointer().address().trunc(width: BitWidth);
2800 });
2801 }
2802
2803 void visitLoadInst(LoadInst &LI) {
2804 auto RetVal = load(Ptr: getValue(V: LI.getPointerOperand()), Alignment: LI.getAlign(),
2805 ValTy: LI.getType(), NoUndef: LI.hasMetadata(KindID: LLVMContext::MD_noundef));
2806 // TODO: track volatile loads
2807 handleMetadata(Ty: LI.getType(), V&: RetVal, I&: LI);
2808 setResult(I&: LI, V: std::move(RetVal));
2809 }
2810
2811 void visitStoreInst(StoreInst &SI) {
2812 auto &Ptr = getValue(V: SI.getPointerOperand());
2813 auto &Val = getValue(V: SI.getValueOperand());
2814 // TODO: track volatile stores
2815 // TODO: handle metadata
2816 store(Ptr, Alignment: SI.getAlign(), Val, ValTy: SI.getValueOperand()->getType());
2817 if (!hasProgramExited() && !Handler.onInstructionExecuted(I&: SI, Result: AnyValue()))
2818 setFailed();
2819 }
2820
2821 void visitInstruction(Instruction &I) {
2822 Handler.onUnrecognizedInstruction(I);
2823 setFailed();
2824 }
2825
2826 void visitExtractValueInst(ExtractValueInst &EVI) {
2827 auto &Res = getValue(V: EVI.getAggregateOperand());
2828 const AnyValue *Pos = &Res;
2829 for (unsigned Idx : EVI.indices())
2830 Pos = &Pos->asAggregate()[Idx];
2831 setResult(I&: EVI, V: *Pos);
2832 }
2833
2834 void visitInsertValueInst(InsertValueInst &IVI) {
2835 AnyValue Res = getValue(V: IVI.getAggregateOperand());
2836 AnyValue *Pos = &Res;
2837 for (unsigned Idx : IVI.indices())
2838 Pos = &Pos->asAggregate()[Idx];
2839 *Pos = getValue(V: IVI.getInsertedValueOperand());
2840 setResult(I&: IVI, V: std::move(Res));
2841 }
2842
2843 void visitInsertElementInst(InsertElementInst &IEI) {
2844 auto Res = getValue(V: IEI.getOperand(i_nocapture: 0));
2845 auto &ResVec = Res.asAggregate();
2846 auto &Idx = getValue(V: IEI.getOperand(i_nocapture: 2));
2847 if (Idx.isPoison() || Idx.asInteger().uge(RHS: ResVec.size())) {
2848 setResult(I&: IEI, V: AnyValue::getPoisonValue(Ctx, Ty: IEI.getType()));
2849 return;
2850 }
2851 ResVec[Idx.asInteger().getZExtValue()] = getValue(V: IEI.getOperand(i_nocapture: 1));
2852 setResult(I&: IEI, V: std::move(Res));
2853 }
2854
2855 void visitExtractElementInst(ExtractElementInst &EEI) {
2856 auto &SrcVec = getValue(V: EEI.getOperand(i_nocapture: 0)).asAggregate();
2857 auto &Idx = getValue(V: EEI.getOperand(i_nocapture: 1));
2858 if (Idx.isPoison() || Idx.asInteger().uge(RHS: SrcVec.size())) {
2859 setResult(I&: EEI, V: AnyValue::getPoisonValue(Ctx, Ty: EEI.getType()));
2860 return;
2861 }
2862 setResult(I&: EEI, V: SrcVec[Idx.asInteger().getZExtValue()]);
2863 }
2864
2865 void visitShuffleVectorInst(ShuffleVectorInst &SVI) {
2866 auto &LHSVec = getValue(V: SVI.getOperand(i_nocapture: 0)).asAggregate();
2867 auto &RHSVec = getValue(V: SVI.getOperand(i_nocapture: 1)).asAggregate();
2868 uint32_t Size = cast<VectorType>(Val: SVI.getOperand(i_nocapture: 0)->getType())
2869 ->getElementCount()
2870 .getKnownMinValue();
2871 std::vector<AnyValue> Res;
2872 uint32_t DstLen = Ctx.getEVL(EC: SVI.getType()->getElementCount());
2873 Res.reserve(n: DstLen);
2874 uint32_t Stride = SVI.getShuffleMask().size();
2875 // For scalable vectors, we need to repeat the shuffle mask until we fill
2876 // the destination vector.
2877 for (uint32_t Off = 0; Off != DstLen; Off += Stride) {
2878 for (int Idx : SVI.getShuffleMask()) {
2879 if (Idx == PoisonMaskElem)
2880 Res.push_back(
2881 x: AnyValue::getPoisonValue(Ctx, Ty: SVI.getType()->getScalarType()));
2882 else if (Idx < static_cast<int>(Size))
2883 Res.push_back(x: LHSVec[Idx]);
2884 else
2885 Res.push_back(x: RHSVec[Idx - Size]);
2886 }
2887 }
2888 setResult(I&: SVI, V: std::move(Res));
2889 }
2890
2891 void visitBitCastInst(BitCastInst &BCI) {
2892 // The conversion is done as if the value had been stored to memory and read
2893 // back as the target type.
2894 SmallVector<Byte> Bytes;
2895 Bytes.resize(N: Ctx.getEffectiveTypeStoreSize(Ty: BCI.getType()),
2896 NV: Byte::concrete(Val: 0));
2897 Ctx.toBytes(Val: getValue(V: BCI.getOperand(i_nocapture: 0)), Ty: BCI.getOperand(i_nocapture: 0)->getType(),
2898 Bytes);
2899 setResult(I&: BCI, V: Ctx.fromBytes(Bytes, Ty: BCI.getType()));
2900 }
2901
2902 void visitFreezeInst(FreezeInst &FI) {
2903 AnyValue Val = getValue(V: FI.getOperand(i_nocapture: 0));
2904 Ctx.freeze(Val, Ty: FI.getType());
2905 setResult(I&: FI, V: std::move(Val));
2906 }
2907
2908 /// This function implements the main interpreter loop.
2909 /// It handles function calls in a non-recursive manner to avoid stack
2910 /// overflows.
2911 ProgramExitInfo runMainLoop() {
2912 uint32_t MaxSteps = Ctx.getMaxSteps();
2913 uint32_t Steps = 0;
2914 while (!hasProgramExited() && !CallStack.empty()) {
2915 Frame &Top = CallStack.back();
2916 CurrentFrame = &Top;
2917 if (Top.State == FrameState::Entry) {
2918 Handler.onFunctionEntry(F&: Top.Func, Args: Top.Args, CallSite: Top.CallSite);
2919 } else {
2920 assert(Top.State == FrameState::Pending &&
2921 "Expected to return from a callee.");
2922 returnFromCallee();
2923 }
2924
2925 Top.State = FrameState::Running;
2926 // Interpreter loop inside a function
2927 while (!hasProgramExited()) {
2928 assert(Top.State == FrameState::Running &&
2929 "Expected to be in running state.");
2930 if (MaxSteps != 0 && Steps >= MaxSteps) {
2931 reportError() << "Exceeded maximum number of execution steps.";
2932 break;
2933 }
2934 ++Steps;
2935
2936 Instruction &I = *Top.PC;
2937 visit(I: &I);
2938 Ctx.resetNoncacheableConstantBuffer();
2939 if (hasProgramExited())
2940 break;
2941
2942 // A function call or return has occurred.
2943 // We need to exit the inner loop and switch to a different frame.
2944 if (Top.State != FrameState::Running)
2945 break;
2946
2947 // Otherwise, move to the next instruction if it is not a terminator.
2948 // For terminators, the PC is updated in the visit* method.
2949 if (!I.isTerminator())
2950 ++Top.PC;
2951 }
2952
2953 if (hasProgramExited())
2954 break;
2955
2956 if (Top.State == FrameState::Exit) {
2957 assert((Top.Func.getReturnType()->isVoidTy() || !Top.RetVal.isNone()) &&
2958 "Expected return value to be set on function exit.");
2959 Handler.onFunctionExit(F&: Top.Func, RetVal: Top.RetVal);
2960 // Free stack objects allocated in this frame.
2961 for (auto &Obj : Top.Allocas)
2962 Ctx.free(Obj: *Obj);
2963 CallStack.pop_back();
2964 } else {
2965 assert(Top.State == FrameState::Pending &&
2966 "Expected to enter a callee.");
2967 }
2968 }
2969 if (!hasProgramExited())
2970 requestProgramExit(Kind: ProgramExitInfo::ProgramExitKind::Returned);
2971 return *getExitInfo();
2972 }
2973};
2974
2975ProgramExitInfo Context::runFunction(Function &F, ArrayRef<AnyValue> Args,
2976 AnyValue &RetVal, EventHandler &Handler) {
2977 InstExecutor Executor(*this, Handler, F, Args, RetVal);
2978 return Executor.runMainLoop();
2979}
2980
2981} // namespace llvm::ubi
2982