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 "Value.h"
16#include "llvm/IR/GetElementPtrTypeIterator.h"
17#include "llvm/IR/InlineAsm.h"
18#include "llvm/IR/InstVisitor.h"
19#include "llvm/IR/Operator.h"
20#include "llvm/IR/PatternMatch.h"
21#include "llvm/Support/Allocator.h"
22
23namespace llvm::ubi {
24
25using namespace PatternMatch;
26
27static AnyValue addNoWrap(const APInt &LHS, const APInt &RHS, bool HasNSW,
28 bool HasNUW) {
29 APInt Res = LHS + RHS;
30 if (HasNUW && Res.ult(RHS))
31 return AnyValue::poison();
32 if (HasNSW && LHS.isNonNegative() == RHS.isNonNegative() &&
33 LHS.isNonNegative() != Res.isNonNegative())
34 return AnyValue::poison();
35 return Res;
36}
37
38static AnyValue subNoWrap(const APInt &LHS, const APInt &RHS, bool HasNSW,
39 bool HasNUW) {
40 APInt Res = LHS - RHS;
41 if (HasNUW && Res.ugt(RHS: LHS))
42 return AnyValue::poison();
43 if (HasNSW && LHS.isNonNegative() != RHS.isNonNegative() &&
44 LHS.isNonNegative() != Res.isNonNegative())
45 return AnyValue::poison();
46 return Res;
47}
48
49static AnyValue mulNoWrap(const APInt &LHS, const APInt &RHS, bool HasNSW,
50 bool HasNUW) {
51 bool Overflow = false;
52 APInt Res = LHS.smul_ov(RHS, Overflow);
53 if (HasNSW && Overflow)
54 return AnyValue::poison();
55 if (HasNUW) {
56 (void)LHS.umul_ov(RHS, Overflow);
57 if (Overflow)
58 return AnyValue::poison();
59 }
60 return Res;
61}
62
63/// Instruction executor using the visitor pattern.
64/// Unlike the Context class that manages the global state,
65/// InstExecutor only maintains the state for call frames.
66class InstExecutor : public InstVisitor<InstExecutor, void>,
67 public ExecutorBase {
68 const DataLayout &DL;
69 std::list<Frame> CallStack;
70 AnyValue None;
71
72 const AnyValue &getValue(Value *V) {
73 if (auto *C = dyn_cast<Constant>(Val: V))
74 return Ctx.getConstantValue(C);
75 return CurrentFrame->ValueMap.at(Val: V);
76 }
77
78 void setResult(Instruction &I, AnyValue V) {
79 if (Status)
80 Status &= Handler.onInstructionExecuted(I, Result: V);
81 CurrentFrame->ValueMap.insert_or_assign(Key: &I, Val: std::move(V));
82 }
83
84 AnyValue computeUnOp(Type *Ty, const AnyValue &Operand,
85 function_ref<AnyValue(const AnyValue &)> ScalarFn) {
86 if (Ty->isVectorTy()) {
87 auto &OperandVec = Operand.asAggregate();
88 std::vector<AnyValue> ResVec;
89 ResVec.reserve(n: OperandVec.size());
90 for (const auto &Scalar : OperandVec)
91 ResVec.push_back(x: ScalarFn(Scalar));
92 return std::move(ResVec);
93 }
94 return ScalarFn(Operand);
95 }
96
97 void visitUnOp(Instruction &I,
98 function_ref<AnyValue(const AnyValue &)> ScalarFn) {
99 setResult(I, V: computeUnOp(Ty: I.getType(), Operand: getValue(V: I.getOperand(i: 0)), ScalarFn));
100 }
101
102 void visitIntUnOp(Instruction &I,
103 function_ref<AnyValue(const APInt &)> ScalarFn) {
104 visitUnOp(I, ScalarFn: [&](const AnyValue &Operand) -> AnyValue {
105 if (Operand.isPoison())
106 return AnyValue::poison();
107 return ScalarFn(Operand.asInteger());
108 });
109 }
110
111 AnyValue computeBinOp(
112 Type *Ty, const AnyValue &LHS, const AnyValue &RHS,
113 function_ref<AnyValue(const AnyValue &, const AnyValue &)> ScalarFn) {
114 if (Ty->isVectorTy()) {
115 auto &LHSVec = LHS.asAggregate();
116 auto &RHSVec = RHS.asAggregate();
117 std::vector<AnyValue> ResVec;
118 ResVec.reserve(n: LHSVec.size());
119 for (const auto &[ScalarLHS, ScalarRHS] : zip(t: LHSVec, u: RHSVec))
120 ResVec.push_back(x: ScalarFn(ScalarLHS, ScalarRHS));
121 return std::move(ResVec);
122 }
123 return ScalarFn(LHS, RHS);
124 }
125
126 void visitBinOp(
127 Instruction &I,
128 function_ref<AnyValue(const AnyValue &, const AnyValue &)> ScalarFn) {
129 setResult(I, V: computeBinOp(Ty: I.getType(), LHS: getValue(V: I.getOperand(i: 0)),
130 RHS: getValue(V: I.getOperand(i: 1)), ScalarFn));
131 }
132
133 void
134 visitIntBinOp(Instruction &I,
135 function_ref<AnyValue(const APInt &, const APInt &)> ScalarFn) {
136 visitBinOp(I, ScalarFn: [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
137 if (LHS.isPoison() || RHS.isPoison())
138 return AnyValue::poison();
139 return ScalarFn(LHS.asInteger(), RHS.asInteger());
140 });
141 }
142
143 void jumpTo(Instruction &Terminator, BasicBlock *DestBB) {
144 if (!Handler.onBBJump(I&: Terminator, To&: *DestBB)) {
145 Status = false;
146 return;
147 }
148 BasicBlock *From = CurrentFrame->BB;
149 CurrentFrame->BB = DestBB;
150 CurrentFrame->PC = DestBB->begin();
151 // Update PHI nodes in batch to avoid the interference between PHI nodes.
152 // We need to store the incoming values into a temporary buffer.
153 // Otherwise, the incoming value may be overwritten before it is
154 // used by other PHI nodes.
155 SmallVector<std::pair<PHINode *, AnyValue>> IncomingValues;
156 PHINode *PHI = nullptr;
157 while ((PHI = dyn_cast<PHINode>(Val&: CurrentFrame->PC))) {
158 Value *Incoming = PHI->getIncomingValueForBlock(BB: From);
159 // TODO: handle fast-math flags.
160 IncomingValues.emplace_back(Args&: PHI, Args: getValue(V: Incoming));
161 ++CurrentFrame->PC;
162 }
163 for (auto &[K, V] : IncomingValues)
164 setResult(I&: *K, V: std::move(V));
165 }
166
167 /// Helper function to determine whether an inline asm is a no-op, which is
168 /// used to implement black_box style optimization blockers.
169 bool isNoopInlineAsm(Value *V, Type *RetTy) {
170 if (auto *Asm = dyn_cast<InlineAsm>(Val: V))
171 return Asm->getAsmString().empty() && RetTy->isVoidTy();
172 return false;
173 }
174
175 AnyValue computePtrAdd(const Pointer &Ptr, const APInt &Offset,
176 GEPNoWrapFlags Flags, AnyValue &AccumulatedOffset) {
177 if (Offset.isZero())
178 return Ptr;
179 APInt IndexBits = Ptr.address().trunc(width: Offset.getBitWidth());
180 auto NewIndex = addNoWrap(LHS: IndexBits, RHS: Offset, /*HasNSW=*/false,
181 HasNUW: Flags.hasNoUnsignedWrap());
182 if (NewIndex.isPoison())
183 return AnyValue::poison();
184 if (Flags.hasNoUnsignedSignedWrap()) {
185 // The successive addition of the current address, truncated to the
186 // pointer index type and interpreted as an unsigned number, and each
187 // offset, interpreted as a signed number, does not wrap the pointer index
188 // type.
189 if (Offset.isNonNegative() ? NewIndex.asInteger().ult(RHS: IndexBits)
190 : NewIndex.asInteger().ugt(RHS: IndexBits))
191 return AnyValue::poison();
192 }
193 APInt NewAddr = Ptr.address();
194 NewAddr.insertBits(SubBits: NewIndex.asInteger(), bitPosition: 0);
195
196 auto *MO = Ptr.getMemoryObject();
197 if (Flags.isInBounds() && (!MO || !MO->inBounds(NewAddr)))
198 return AnyValue::poison();
199
200 if (!AccumulatedOffset.isPoison()) {
201 AccumulatedOffset =
202 addNoWrap(LHS: AccumulatedOffset.asInteger(), RHS: Offset,
203 HasNSW: Flags.hasNoUnsignedSignedWrap(), HasNUW: Flags.hasNoUnsignedWrap());
204 if (AccumulatedOffset.isPoison())
205 return AnyValue::poison();
206 }
207
208 // Should not expose provenance here even if the new address doesn't point
209 // to the original object.
210 return Ptr.getWithNewAddr(NewAddr);
211 }
212
213 AnyValue computePtrAdd(const AnyValue &Ptr, const APInt &Offset,
214 GEPNoWrapFlags Flags, AnyValue &AccumulatedOffset) {
215 if (Ptr.isPoison())
216 return AnyValue::poison();
217 return computePtrAdd(Ptr: Ptr.asPointer(), Offset, Flags, AccumulatedOffset);
218 }
219
220 AnyValue computeScaledPtrAdd(const AnyValue &Ptr, const AnyValue &Index,
221 const APInt &Scale, GEPNoWrapFlags Flags,
222 AnyValue &AccumulatedOffset) {
223 if (Ptr.isPoison() || Index.isPoison())
224 return AnyValue::poison();
225 assert(Ptr.isPointer() && Index.isInteger() && "Unexpected type.");
226 if (Scale.isOne())
227 return computePtrAdd(Ptr, Offset: Index.asInteger(), Flags, AccumulatedOffset);
228 auto ScaledOffset =
229 mulNoWrap(LHS: Index.asInteger(), RHS: Scale, HasNSW: Flags.hasNoUnsignedSignedWrap(),
230 HasNUW: Flags.hasNoUnsignedWrap());
231 if (ScaledOffset.isPoison())
232 return AnyValue::poison();
233 return computePtrAdd(Ptr, Offset: ScaledOffset.asInteger(), Flags,
234 AccumulatedOffset);
235 }
236
237 AnyValue canonicalizeIndex(const AnyValue &Idx, unsigned IndexBitWidth,
238 GEPNoWrapFlags Flags) {
239 if (Idx.isPoison())
240 return AnyValue::poison();
241 auto &IdxInt = Idx.asInteger();
242 if (IdxInt.getBitWidth() == IndexBitWidth)
243 return Idx;
244 if (IdxInt.getBitWidth() > IndexBitWidth) {
245 if (Flags.hasNoUnsignedSignedWrap() &&
246 !IdxInt.isSignedIntN(N: IndexBitWidth))
247 return AnyValue::poison();
248
249 if (Flags.hasNoUnsignedWrap() && !IdxInt.isIntN(N: IndexBitWidth))
250 return AnyValue::poison();
251
252 return IdxInt.trunc(width: IndexBitWidth);
253 }
254 return IdxInt.sext(width: IndexBitWidth);
255 }
256
257public:
258 InstExecutor(Context &C, EventHandler &H, Function &F,
259 ArrayRef<AnyValue> Args, AnyValue &RetVal)
260 : ExecutorBase(C, H), DL(Ctx.getDataLayout()) {
261 CallStack.emplace_back(args&: F, /*CallSite=*/args: nullptr, /*LastFrame=*/args: nullptr, args&: Args,
262 args&: RetVal, args: Ctx.getTLIImpl());
263 }
264
265 void visitReturnInst(ReturnInst &RI) {
266 if (auto *RV = RI.getReturnValue())
267 CurrentFrame->RetVal = getValue(V: RV);
268 CurrentFrame->State = FrameState::Exit;
269 Status &= Handler.onInstructionExecuted(I&: RI, Result: None);
270 }
271
272 void visitUncondBrInst(UncondBrInst &BI) { jumpTo(Terminator&: BI, DestBB: BI.getSuccessor()); }
273
274 void visitCondBrInst(CondBrInst &BI) {
275 switch (getValue(V: BI.getCondition()).asBoolean()) {
276 case BooleanKind::True:
277 jumpTo(Terminator&: BI, DestBB: BI.getSuccessor(i: 0));
278 return;
279 case BooleanKind::False:
280 jumpTo(Terminator&: BI, DestBB: BI.getSuccessor(i: 1));
281 return;
282 case BooleanKind::Poison:
283 reportImmediateUB(Msg: "Branch on poison condition.");
284 return;
285 }
286 }
287
288 void visitSwitchInst(SwitchInst &SI) {
289 auto &Cond = getValue(V: SI.getCondition());
290 if (Cond.isPoison()) {
291 reportImmediateUB(Msg: "Switch on poison condition.");
292 return;
293 }
294 for (auto &Case : SI.cases()) {
295 if (Case.getCaseValue()->getValue() == Cond.asInteger()) {
296 jumpTo(Terminator&: SI, DestBB: Case.getCaseSuccessor());
297 return;
298 }
299 }
300 jumpTo(Terminator&: SI, DestBB: SI.getDefaultDest());
301 }
302
303 void visitUnreachableInst(UnreachableInst &) {
304 reportImmediateUB(Msg: "Unreachable code.");
305 }
306
307 void visitCallBrInst(CallBrInst &CI) {
308 if (isNoopInlineAsm(V: CI.getCalledOperand(), RetTy: CI.getType())) {
309 jumpTo(Terminator&: CI, DestBB: CI.getDefaultDest());
310 return;
311 }
312
313 Handler.onUnrecognizedInstruction(I&: CI);
314 Status = false;
315 }
316
317 void visitIndirectBrInst(IndirectBrInst &IBI) {
318 auto &Target = getValue(V: IBI.getAddress());
319 if (Target.isPoison()) {
320 reportImmediateUB(Msg: "Indirect branch on poison.");
321 return;
322 }
323 if (BasicBlock *DestBB = Ctx.getTargetBlock(Ptr: Target.asPointer())) {
324 if (any_of(Range: IBI.successors(),
325 P: [DestBB](BasicBlock *Succ) { return Succ == DestBB; }))
326 jumpTo(Terminator&: IBI, DestBB);
327 else
328 reportImmediateUB(Msg: "Indirect branch on unlisted target BB.");
329
330 return;
331 }
332 reportImmediateUB(Msg: "Indirect branch on invalid target BB.");
333 }
334
335 void returnFromCallee() {
336 // TODO: handle retval attributes (Attributes from known callee should be
337 // applied if available).
338 // TODO: handle metadata
339 auto &CB = cast<CallBase>(Val&: *CurrentFrame->PC);
340 CurrentFrame->CalleeArgs.clear();
341 AnyValue &RetVal = CurrentFrame->CalleeRetVal;
342 setResult(I&: CB, V: std::move(RetVal));
343
344 if (auto *II = dyn_cast<InvokeInst>(Val: &CB))
345 jumpTo(Terminator&: *II, DestBB: II->getNormalDest());
346 else if (CurrentFrame->State == FrameState::Pending)
347 ++CurrentFrame->PC;
348 }
349
350 AnyValue callIntrinsic(CallBase &CB) {
351 Intrinsic::ID IID = CB.getIntrinsicID();
352 switch (IID) {
353 case Intrinsic::assume:
354 switch (getValue(V: CB.getArgOperand(i: 0)).asBoolean()) {
355 case BooleanKind::True:
356 break;
357 case BooleanKind::False:
358 case BooleanKind::Poison:
359 reportImmediateUB(Msg: "Assume on false or poison condition.");
360 break;
361 }
362 // TODO: handle llvm.assume with operand bundles
363 return AnyValue();
364 case Intrinsic::lifetime_start:
365 case Intrinsic::lifetime_end: {
366 auto *Ptr = CB.getArgOperand(i: 0);
367 if (isa<PoisonValue>(Val: Ptr))
368 return AnyValue();
369 auto *MO = getValue(V: Ptr).asPointer().getMemoryObject();
370 assert(MO && "Memory object accessed by lifetime intrinsic should be "
371 "always valid.");
372 if (IID == Intrinsic::lifetime_start) {
373 MO->setState(MemoryObjectState::Alive);
374 fill(Range: MO->getBytes(), Value: Byte::undef());
375 } else {
376 MO->setState(MemoryObjectState::Dead);
377 }
378 return AnyValue();
379 }
380 default:
381 Handler.onUnrecognizedInstruction(I&: CB);
382 Status = false;
383 return AnyValue();
384 }
385 }
386
387 AnyValue callLibFunc(CallBase &CB, Function *ResolvedCallee) {
388 LibFunc LF;
389 // Respect nobuiltin attributes on call site.
390 if (CB.isNoBuiltin() ||
391 !CurrentFrame->TLI.getLibFunc(FDecl: *ResolvedCallee, F&: LF)) {
392 Handler.onUnrecognizedInstruction(I&: CB);
393 Status = false;
394 return AnyValue();
395 }
396
397 Handler.onUnrecognizedInstruction(I&: CB);
398 Status = false;
399 return AnyValue();
400 }
401
402 void enterCall(CallBase &CB) {
403 Function *Callee = CB.getCalledFunction();
404 // TODO: handle parameter attributes (Attributes from known callee should be
405 // applied if available).
406 // TODO: handle byval/initializes
407 auto &CalleeArgs = CurrentFrame->CalleeArgs;
408 assert(CalleeArgs.empty() &&
409 "Forgot to call returnFromCallee before entering a new call.");
410 for (Value *Arg : CB.args())
411 CalleeArgs.push_back(Elt: getValue(V: Arg));
412
413 if (!Callee) {
414 Value *CalledOperand = CB.getCalledOperand();
415 if (isNoopInlineAsm(V: CalledOperand, RetTy: CB.getType())) {
416 CurrentFrame->ResolvedCallee = nullptr;
417 returnFromCallee();
418 return;
419 }
420
421 if (isa<InlineAsm>(Val: CalledOperand)) {
422 Handler.onUnrecognizedInstruction(I&: CB);
423 Status = false;
424 return;
425 }
426
427 auto &CalleeVal = getValue(V: CalledOperand);
428 if (CalleeVal.isPoison()) {
429 reportImmediateUB(Msg: "Indirect call through poison function pointer.");
430 return;
431 }
432 Callee = Ctx.getTargetFunction(Ptr: CalleeVal.asPointer());
433 if (!Callee) {
434 reportImmediateUB(Msg: "Indirect call through invalid function pointer.");
435 return;
436 }
437 if (Callee->getFunctionType() != CB.getFunctionType()) {
438 reportImmediateUB(Msg: "Indirect call through a function pointer with "
439 "mismatched signature.");
440 return;
441 }
442 }
443
444 assert(Callee && "Expected a resolved callee function.");
445 assert(
446 Callee->getFunctionType() == CB.getFunctionType() &&
447 "Expected the callee function type to match the call site signature.");
448 CurrentFrame->ResolvedCallee = Callee;
449 if (Callee->isIntrinsic()) {
450 CurrentFrame->CalleeRetVal = callIntrinsic(CB);
451 returnFromCallee();
452 return;
453 } else if (Callee->isDeclaration()) {
454 CurrentFrame->CalleeRetVal = callLibFunc(CB, ResolvedCallee: Callee);
455 returnFromCallee();
456 return;
457 } else {
458 uint32_t MaxStackDepth = Ctx.getMaxStackDepth();
459 if (MaxStackDepth && CallStack.size() >= MaxStackDepth) {
460 reportError(Msg: "Maximum stack depth exceeded.");
461 return;
462 }
463 assert(!Callee->empty() && "Expected a defined function.");
464 // Suspend the current frame and push the callee frame onto the stack.
465 ArrayRef<AnyValue> Args = CurrentFrame->CalleeArgs;
466 AnyValue &RetVal = CurrentFrame->CalleeRetVal;
467 CurrentFrame->State = FrameState::Pending;
468 CallStack.emplace_back(args&: *Callee, args: &CB, args&: CurrentFrame, args&: Args, args&: RetVal,
469 args: Ctx.getTLIImpl());
470 }
471 }
472
473 void visitCallInst(CallInst &CI) { enterCall(CB&: CI); }
474
475 void visitInvokeInst(InvokeInst &II) {
476 // TODO: handle exceptions
477 enterCall(CB&: II);
478 }
479
480 void visitAdd(BinaryOperator &I) {
481 visitIntBinOp(I, ScalarFn: [&](const APInt &LHS, const APInt &RHS) {
482 return addNoWrap(LHS, RHS, HasNSW: I.hasNoSignedWrap(), HasNUW: I.hasNoUnsignedWrap());
483 });
484 }
485
486 void visitSub(BinaryOperator &I) {
487 visitIntBinOp(I, ScalarFn: [&](const APInt &LHS, const APInt &RHS) {
488 return subNoWrap(LHS, RHS, HasNSW: I.hasNoSignedWrap(), HasNUW: I.hasNoUnsignedWrap());
489 });
490 }
491
492 void visitMul(BinaryOperator &I) {
493 visitIntBinOp(I, ScalarFn: [&](const APInt &LHS, const APInt &RHS) {
494 return mulNoWrap(LHS, RHS, HasNSW: I.hasNoSignedWrap(), HasNUW: I.hasNoUnsignedWrap());
495 });
496 }
497
498 void visitSDiv(BinaryOperator &I) {
499 visitBinOp(I, ScalarFn: [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
500 // Priority: Immediate UB > poison > normal value
501 if (RHS.isPoison()) {
502 reportImmediateUB(Msg: "Division by zero (refine RHS to 0).");
503 return AnyValue::poison();
504 }
505 const APInt &RHSVal = RHS.asInteger();
506 if (RHSVal.isZero()) {
507 reportImmediateUB(Msg: "Division by zero.");
508 return AnyValue::poison();
509 }
510 if (LHS.isPoison()) {
511 if (RHSVal.isAllOnes())
512 reportImmediateUB(
513 Msg: "Signed division overflow (refine LHS to INT_MIN).");
514 return AnyValue::poison();
515 }
516 const APInt &LHSVal = LHS.asInteger();
517 if (LHSVal.isMinSignedValue() && RHSVal.isAllOnes()) {
518 reportImmediateUB(Msg: "Signed division overflow.");
519 return AnyValue::poison();
520 }
521
522 if (I.isExact()) {
523 APInt Q, R;
524 APInt::sdivrem(LHS: LHSVal, RHS: RHSVal, Quotient&: Q, Remainder&: R);
525 if (!R.isZero())
526 return AnyValue::poison();
527 return Q;
528 } else {
529 return LHSVal.sdiv(RHS: RHSVal);
530 }
531 });
532 }
533
534 void visitSRem(BinaryOperator &I) {
535 visitBinOp(I, ScalarFn: [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
536 // Priority: Immediate UB > poison > normal value
537 if (RHS.isPoison()) {
538 reportImmediateUB(Msg: "Division by zero (refine RHS to 0).");
539 return AnyValue::poison();
540 }
541 const APInt &RHSVal = RHS.asInteger();
542 if (RHSVal.isZero()) {
543 reportImmediateUB(Msg: "Division by zero.");
544 return AnyValue::poison();
545 }
546 if (LHS.isPoison()) {
547 if (RHSVal.isAllOnes())
548 reportImmediateUB(
549 Msg: "Signed division overflow (refine LHS to INT_MIN).");
550 return AnyValue::poison();
551 }
552 const APInt &LHSVal = LHS.asInteger();
553 if (LHSVal.isMinSignedValue() && RHSVal.isAllOnes()) {
554 reportImmediateUB(Msg: "Signed division overflow.");
555 return AnyValue::poison();
556 }
557
558 return LHSVal.srem(RHS: RHSVal);
559 });
560 }
561
562 void visitUDiv(BinaryOperator &I) {
563 visitBinOp(I, ScalarFn: [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
564 // Priority: Immediate UB > poison > normal value
565 if (RHS.isPoison()) {
566 reportImmediateUB(Msg: "Division by zero (refine RHS to 0).");
567 return AnyValue::poison();
568 }
569 const APInt &RHSVal = RHS.asInteger();
570 if (RHSVal.isZero()) {
571 reportImmediateUB(Msg: "Division by zero.");
572 return AnyValue::poison();
573 }
574 if (LHS.isPoison())
575 return AnyValue::poison();
576 const APInt &LHSVal = LHS.asInteger();
577
578 if (I.isExact()) {
579 APInt Q, R;
580 APInt::udivrem(LHS: LHSVal, RHS: RHSVal, Quotient&: Q, Remainder&: R);
581 if (!R.isZero())
582 return AnyValue::poison();
583 return Q;
584 } else {
585 return LHSVal.udiv(RHS: RHSVal);
586 }
587 });
588 }
589
590 void visitURem(BinaryOperator &I) {
591 visitBinOp(I, ScalarFn: [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
592 // Priority: Immediate UB > poison > normal value
593 if (RHS.isPoison()) {
594 reportImmediateUB(Msg: "Division by zero (refine RHS to 0).");
595 return AnyValue::poison();
596 }
597 const APInt &RHSVal = RHS.asInteger();
598 if (RHSVal.isZero()) {
599 reportImmediateUB(Msg: "Division by zero.");
600 return AnyValue::poison();
601 }
602 if (LHS.isPoison())
603 return AnyValue::poison();
604 const APInt &LHSVal = LHS.asInteger();
605 return LHSVal.urem(RHS: RHSVal);
606 });
607 }
608
609 void visitTruncInst(TruncInst &Trunc) {
610 visitIntUnOp(I&: Trunc, ScalarFn: [&](const APInt &Operand) -> AnyValue {
611 unsigned DestBW = Trunc.getType()->getScalarSizeInBits();
612 if (Trunc.hasNoSignedWrap() && Operand.getSignificantBits() > DestBW)
613 return AnyValue::poison();
614 if (Trunc.hasNoUnsignedWrap() && Operand.getActiveBits() > DestBW)
615 return AnyValue::poison();
616 return Operand.trunc(width: DestBW);
617 });
618 }
619
620 void visitZExtInst(ZExtInst &ZExt) {
621 visitIntUnOp(I&: ZExt, ScalarFn: [&](const APInt &Operand) -> AnyValue {
622 uint32_t DestBW = ZExt.getDestTy()->getScalarSizeInBits();
623 if (ZExt.hasNonNeg() && Operand.isNegative())
624 return AnyValue::poison();
625 return Operand.zext(width: DestBW);
626 });
627 }
628
629 void visitSExtInst(SExtInst &SExt) {
630 visitIntUnOp(I&: SExt, ScalarFn: [&](const APInt &Operand) -> AnyValue {
631 uint32_t DestBW = SExt.getDestTy()->getScalarSizeInBits();
632 return Operand.sext(width: DestBW);
633 });
634 }
635
636 void visitAnd(BinaryOperator &I) {
637 visitIntBinOp(I, ScalarFn: [](const APInt &LHS, const APInt &RHS) -> AnyValue {
638 return LHS & RHS;
639 });
640 }
641
642 void visitXor(BinaryOperator &I) {
643 visitIntBinOp(I, ScalarFn: [](const APInt &LHS, const APInt &RHS) -> AnyValue {
644 return LHS ^ RHS;
645 });
646 }
647
648 void visitOr(BinaryOperator &I) {
649 visitIntBinOp(I, ScalarFn: [&](const APInt &LHS, const APInt &RHS) -> AnyValue {
650 if (cast<PossiblyDisjointInst>(Val&: I).isDisjoint() && LHS.intersects(RHS))
651 return AnyValue::poison();
652 return LHS | RHS;
653 });
654 }
655
656 void visitShl(BinaryOperator &I) {
657 visitIntBinOp(I, ScalarFn: [&](const APInt &LHS, const APInt &RHS) -> AnyValue {
658 if (RHS.uge(RHS: LHS.getBitWidth()))
659 return AnyValue::poison();
660 if (I.hasNoSignedWrap() && RHS.uge(RHS: LHS.getNumSignBits()))
661 return AnyValue::poison();
662 if (I.hasNoUnsignedWrap() && RHS.ugt(RHS: LHS.countl_zero()))
663 return AnyValue::poison();
664 return LHS.shl(ShiftAmt: RHS);
665 });
666 }
667
668 void visitLShr(BinaryOperator &I) {
669 visitIntBinOp(I, ScalarFn: [&](const APInt &LHS, const APInt &RHS) -> AnyValue {
670 if (RHS.uge(RHS: cast<PossiblyExactOperator>(Val&: I).isExact()
671 ? LHS.countr_zero() + 1
672 : LHS.getBitWidth()))
673 return AnyValue::poison();
674 return LHS.lshr(ShiftAmt: RHS);
675 });
676 }
677
678 void visitAShr(BinaryOperator &I) {
679 visitIntBinOp(I, ScalarFn: [&](const APInt &LHS, const APInt &RHS) -> AnyValue {
680 if (RHS.uge(RHS: cast<PossiblyExactOperator>(Val&: I).isExact()
681 ? LHS.countr_zero() + 1
682 : LHS.getBitWidth()))
683 return AnyValue::poison();
684 return LHS.ashr(ShiftAmt: RHS);
685 });
686 }
687
688 void visitICmpInst(ICmpInst &I) {
689 visitBinOp(I, ScalarFn: [&](const AnyValue &LHS, const AnyValue &RHS) -> AnyValue {
690 if (LHS.isPoison() || RHS.isPoison())
691 return AnyValue::poison();
692 // TODO: handle pointer comparison.
693 const APInt &LHSVal = LHS.asInteger();
694 const APInt &RHSVal = RHS.asInteger();
695 if (I.hasSameSign() && LHSVal.isNonNegative() != RHSVal.isNonNegative())
696 return AnyValue::poison();
697 return AnyValue::boolean(
698 Val: ICmpInst::compare(LHS: LHSVal, RHS: RHSVal, Pred: I.getPredicate()));
699 });
700 }
701
702 void visitSelect(SelectInst &SI) {
703 // TODO: handle fast-math flags.
704 if (SI.getCondition()->getType()->isIntegerTy(Bitwidth: 1)) {
705 switch (getValue(V: SI.getCondition()).asBoolean()) {
706 case BooleanKind::True:
707 setResult(I&: SI, V: getValue(V: SI.getTrueValue()));
708 return;
709 case BooleanKind::False:
710 setResult(I&: SI, V: getValue(V: SI.getFalseValue()));
711 return;
712 case BooleanKind::Poison:
713 setResult(I&: SI, V: AnyValue::getPoisonValue(Ctx, Ty: SI.getType()));
714 return;
715 }
716 }
717
718 auto &Cond = getValue(V: SI.getCondition()).asAggregate();
719 auto &TV = getValue(V: SI.getTrueValue()).asAggregate();
720 auto &FV = getValue(V: SI.getFalseValue()).asAggregate();
721 std::vector<AnyValue> Res;
722 size_t Len = Cond.size();
723 Res.reserve(n: Len);
724 for (uint32_t I = 0; I != Len; ++I) {
725 switch (Cond[I].asBoolean()) {
726 case BooleanKind::True:
727 Res.push_back(x: TV[I]);
728 break;
729 case BooleanKind::False:
730 Res.push_back(x: FV[I]);
731 break;
732 case BooleanKind::Poison:
733 Res.push_back(x: AnyValue::poison());
734 break;
735 }
736 }
737 setResult(I&: SI, V: std::move(Res));
738 }
739
740 void visitAllocaInst(AllocaInst &AI) {
741 uint64_t AllocSize = Ctx.getEffectiveTypeAllocSize(Ty: AI.getAllocatedType());
742 if (AI.isArrayAllocation()) {
743 auto &Size = getValue(V: AI.getArraySize());
744 if (Size.isPoison()) {
745 reportImmediateUB(Msg: "Alloca with poison array size.");
746 return;
747 }
748 if (Size.asInteger().getActiveBits() > 64) {
749 reportImmediateUB(
750 Msg: "Alloca with large array size that overflows uint64_t.");
751 return;
752 }
753 bool Overflowed = false;
754 AllocSize = SaturatingMultiply(X: AllocSize, Y: Size.asInteger().getZExtValue(),
755 ResultOverflowed: &Overflowed);
756 if (Overflowed) {
757 reportImmediateUB(
758 Msg: "Alloca with allocation size that overflows uint64_t.");
759 return;
760 }
761 }
762 // If it is used by llvm.lifetime.start, it should be initially dead.
763 bool IsInitiallyDead = any_of(Range: AI.users(), P: [](User *U) {
764 return match(V: U, P: m_Intrinsic<Intrinsic::lifetime_start>());
765 });
766 auto Obj = Ctx.allocate(Size: AllocSize, Align: AI.getPointerAlignment(DL).value(),
767 Name: AI.getName(), AS: AI.getAddressSpace(),
768 InitKind: IsInitiallyDead ? MemInitKind::Poisoned
769 : MemInitKind::Uninitialized);
770 if (!Obj) {
771 reportError(Msg: "Insufficient stack space.");
772 return;
773 }
774 CurrentFrame->Allocas.push_back(Elt: Obj);
775 setResult(I&: AI, V: Ctx.deriveFromMemoryObject(Obj));
776 }
777
778 void visitGetElementPtrInst(GetElementPtrInst &GEP) {
779 uint32_t IndexBitWidth =
780 DL.getIndexSizeInBits(AS: GEP.getType()->getPointerAddressSpace());
781 GEPNoWrapFlags Flags = GEP.getNoWrapFlags();
782 AnyValue Res = getValue(V: GEP.getPointerOperand());
783 AnyValue AccumulatedOffset = APInt(IndexBitWidth, 0);
784 if (Res.isAggregate())
785 AccumulatedOffset =
786 AnyValue::getVectorSplat(Scalar: AccumulatedOffset, NumElements: Res.asAggregate().size());
787 auto ApplyScaledOffset = [&](const AnyValue &Index, const APInt &Scale) {
788 if (Index.isAggregate() && !Res.isAggregate()) {
789 Res = AnyValue::getVectorSplat(Scalar: Res, NumElements: Index.asAggregate().size());
790 AccumulatedOffset = AnyValue::getVectorSplat(
791 Scalar: AccumulatedOffset, NumElements: Index.asAggregate().size());
792 }
793 if (Index.isAggregate() && Res.isAggregate()) {
794 for (auto &&[ResElem, IndexElem, OffsetElem] :
795 zip(t&: Res.asAggregate(), u: Index.asAggregate(),
796 args&: AccumulatedOffset.asAggregate()))
797 ResElem = computeScaledPtrAdd(
798 Ptr: ResElem, Index: canonicalizeIndex(Idx: IndexElem, IndexBitWidth, Flags),
799 Scale, Flags, AccumulatedOffset&: OffsetElem);
800 } else {
801 AnyValue CanonicalIndex =
802 canonicalizeIndex(Idx: Index, IndexBitWidth, Flags);
803 if (Res.isAggregate()) {
804 for (auto &&[ResElem, OffsetElem] :
805 zip(t&: Res.asAggregate(), u&: AccumulatedOffset.asAggregate()))
806 ResElem = computeScaledPtrAdd(Ptr: ResElem, Index: CanonicalIndex, Scale, Flags,
807 AccumulatedOffset&: OffsetElem);
808 } else {
809 Res = computeScaledPtrAdd(Ptr: Res, Index: CanonicalIndex, Scale, Flags,
810 AccumulatedOffset);
811 }
812 }
813 };
814
815 for (gep_type_iterator GTI = gep_type_begin(GEP), GTE = gep_type_end(GEP);
816 GTI != GTE; ++GTI) {
817 Value *V = GTI.getOperand();
818
819 // Fast path for zero offsets.
820 if (auto *CI = dyn_cast<ConstantInt>(Val: V)) {
821 if (CI->isZero())
822 continue;
823 }
824 if (isa<ConstantAggregateZero>(Val: V))
825 continue;
826
827 // Handle a struct index, which adds its field offset to the pointer.
828 if (StructType *STy = GTI.getStructTypeOrNull()) {
829 unsigned ElementIdx = cast<ConstantInt>(Val: V)->getZExtValue();
830 const StructLayout *SL = DL.getStructLayout(Ty: STy);
831 // Element offset is in bytes.
832 ApplyScaledOffset(
833 APInt(IndexBitWidth, SL->getElementOffset(Idx: ElementIdx)),
834 APInt(IndexBitWidth, 1));
835 continue;
836 }
837
838 // Truncate if type size exceeds index space.
839 // TODO: Should be documented in LangRef: GEPs with nowrap flags should
840 // return poison when the type size exceeds index space.
841 TypeSize Offset = GTI.getSequentialElementStride(DL);
842 APInt Scale(IndexBitWidth, Ctx.getEffectiveTypeSize(Size: Offset),
843 /*isSigned=*/false, /*implicitTrunc=*/true);
844 if (!Scale.isZero())
845 ApplyScaledOffset(getValue(V), Scale);
846 }
847
848 setResult(I&: GEP, V: std::move(Res));
849 }
850
851 void visitIntToPtr(IntToPtrInst &I) {
852 return visitUnOp(I, ScalarFn: [&](const AnyValue &V) -> AnyValue {
853 if (V.isPoison())
854 return AnyValue::poison();
855 // TODO: expose provenance
856 // TODO: check metadata
857 return Pointer(V.asInteger().zextOrTrunc(
858 width: DL.getPointerSizeInBits(AS: I.getType()->getPointerAddressSpace())));
859 });
860 }
861
862 void visitLoadInst(LoadInst &LI) {
863 auto RetVal =
864 load(Ptr: getValue(V: LI.getPointerOperand()), Alignment: LI.getAlign(), ValTy: LI.getType());
865 // TODO: track volatile loads
866 // TODO: handle metadata
867 setResult(I&: LI, V: std::move(RetVal));
868 }
869
870 void visitStoreInst(StoreInst &SI) {
871 auto &Ptr = getValue(V: SI.getPointerOperand());
872 auto &Val = getValue(V: SI.getValueOperand());
873 // TODO: track volatile stores
874 // TODO: handle metadata
875 store(Ptr, Alignment: SI.getAlign(), Val, ValTy: SI.getValueOperand()->getType());
876 if (Status)
877 Status &= Handler.onInstructionExecuted(I&: SI, Result: AnyValue());
878 }
879
880 void visitInstruction(Instruction &I) {
881 Handler.onUnrecognizedInstruction(I);
882 Status = false;
883 }
884
885 void visitExtractValueInst(ExtractValueInst &EVI) {
886 auto &Res = getValue(V: EVI.getAggregateOperand());
887 const AnyValue *Pos = &Res;
888 for (unsigned Idx : EVI.indices())
889 Pos = &Pos->asAggregate()[Idx];
890 setResult(I&: EVI, V: *Pos);
891 }
892
893 void visitInsertValueInst(InsertValueInst &IVI) {
894 AnyValue Res = getValue(V: IVI.getAggregateOperand());
895 AnyValue *Pos = &Res;
896 for (unsigned Idx : IVI.indices())
897 Pos = &Pos->asAggregate()[Idx];
898 *Pos = getValue(V: IVI.getInsertedValueOperand());
899 setResult(I&: IVI, V: std::move(Res));
900 }
901
902 void visitInsertElementInst(InsertElementInst &IEI) {
903 auto Res = getValue(V: IEI.getOperand(i_nocapture: 0));
904 auto &ResVec = Res.asAggregate();
905 auto &Idx = getValue(V: IEI.getOperand(i_nocapture: 2));
906 if (Idx.isPoison() || Idx.asInteger().uge(RHS: ResVec.size())) {
907 setResult(I&: IEI, V: AnyValue::getPoisonValue(Ctx, Ty: IEI.getType()));
908 return;
909 }
910 ResVec[Idx.asInteger().getZExtValue()] = getValue(V: IEI.getOperand(i_nocapture: 1));
911 setResult(I&: IEI, V: std::move(Res));
912 }
913
914 void visitExtractElementInst(ExtractElementInst &EEI) {
915 auto &SrcVec = getValue(V: EEI.getOperand(i_nocapture: 0)).asAggregate();
916 auto &Idx = getValue(V: EEI.getOperand(i_nocapture: 1));
917 if (Idx.isPoison() || Idx.asInteger().uge(RHS: SrcVec.size())) {
918 setResult(I&: EEI, V: AnyValue::getPoisonValue(Ctx, Ty: EEI.getType()));
919 return;
920 }
921 setResult(I&: EEI, V: SrcVec[Idx.asInteger().getZExtValue()]);
922 }
923
924 void visitShuffleVectorInst(ShuffleVectorInst &SVI) {
925 auto &LHSVec = getValue(V: SVI.getOperand(i_nocapture: 0)).asAggregate();
926 auto &RHSVec = getValue(V: SVI.getOperand(i_nocapture: 1)).asAggregate();
927 uint32_t Size = cast<VectorType>(Val: SVI.getOperand(i_nocapture: 0)->getType())
928 ->getElementCount()
929 .getKnownMinValue();
930 std::vector<AnyValue> Res;
931 uint32_t DstLen = Ctx.getEVL(EC: SVI.getType()->getElementCount());
932 Res.reserve(n: DstLen);
933 uint32_t Stride = SVI.getShuffleMask().size();
934 // For scalable vectors, we need to repeat the shuffle mask until we fill
935 // the destination vector.
936 for (uint32_t Off = 0; Off != DstLen; Off += Stride) {
937 for (int Idx : SVI.getShuffleMask()) {
938 if (Idx == PoisonMaskElem)
939 Res.push_back(x: AnyValue::poison());
940 else if (Idx < static_cast<int>(Size))
941 Res.push_back(x: LHSVec[Idx]);
942 else
943 Res.push_back(x: RHSVec[Idx - Size]);
944 }
945 }
946 setResult(I&: SVI, V: std::move(Res));
947 }
948
949 void visitBitCastInst(BitCastInst &BCI) {
950 // The conversion is done as if the value had been stored to memory and read
951 // back as the target type.
952 SmallVector<Byte> Bytes;
953 Bytes.resize(N: Ctx.getEffectiveTypeStoreSize(Ty: BCI.getType()),
954 NV: Byte::concrete(Val: 0));
955 Ctx.toBytes(Val: getValue(V: BCI.getOperand(i_nocapture: 0)), Ty: BCI.getOperand(i_nocapture: 0)->getType(),
956 Bytes);
957 setResult(I&: BCI, V: Ctx.fromBytes(Bytes, Ty: BCI.getType()));
958 }
959
960 void visitFreezeInst(FreezeInst &FI) {
961 AnyValue Val = getValue(V: FI.getOperand(i_nocapture: 0));
962 Ctx.freeze(Val, Ty: FI.getType());
963 setResult(I&: FI, V: std::move(Val));
964 }
965
966 /// This function implements the main interpreter loop.
967 /// It handles function calls in a non-recursive manner to avoid stack
968 /// overflows.
969 bool runMainLoop() {
970 uint32_t MaxSteps = Ctx.getMaxSteps();
971 uint32_t Steps = 0;
972 while (Status && !CallStack.empty()) {
973 Frame &Top = CallStack.back();
974 CurrentFrame = &Top;
975 if (Top.State == FrameState::Entry) {
976 Handler.onFunctionEntry(F&: Top.Func, Args: Top.Args, CallSite: Top.CallSite);
977 } else {
978 assert(Top.State == FrameState::Pending &&
979 "Expected to return from a callee.");
980 returnFromCallee();
981 }
982
983 Top.State = FrameState::Running;
984 // Interpreter loop inside a function
985 while (Status) {
986 assert(Top.State == FrameState::Running &&
987 "Expected to be in running state.");
988 if (MaxSteps != 0 && Steps >= MaxSteps) {
989 reportError(Msg: "Exceeded maximum number of execution steps.");
990 break;
991 }
992 ++Steps;
993
994 Instruction &I = *Top.PC;
995 visit(I: &I);
996 if (!Status)
997 break;
998
999 // A function call or return has occurred.
1000 // We need to exit the inner loop and switch to a different frame.
1001 if (Top.State != FrameState::Running)
1002 break;
1003
1004 // Otherwise, move to the next instruction if it is not a terminator.
1005 // For terminators, the PC is updated in the visit* method.
1006 if (!I.isTerminator())
1007 ++Top.PC;
1008 }
1009
1010 if (!Status)
1011 break;
1012
1013 if (Top.State == FrameState::Exit) {
1014 assert((Top.Func.getReturnType()->isVoidTy() || !Top.RetVal.isNone()) &&
1015 "Expected return value to be set on function exit.");
1016 Handler.onFunctionExit(F&: Top.Func, RetVal: Top.RetVal);
1017 // Free stack objects allocated in this frame.
1018 for (auto &Obj : Top.Allocas)
1019 Ctx.free(Address: Obj->getAddress());
1020 CallStack.pop_back();
1021 } else {
1022 assert(Top.State == FrameState::Pending &&
1023 "Expected to enter a callee.");
1024 }
1025 }
1026 return Status;
1027 }
1028};
1029
1030bool Context::runFunction(Function &F, ArrayRef<AnyValue> Args,
1031 AnyValue &RetVal, EventHandler &Handler) {
1032 InstExecutor Executor(*this, Handler, F, Args, RetVal);
1033 return Executor.runMainLoop();
1034}
1035
1036} // namespace llvm::ubi
1037