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