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