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