1//===- Context.cpp - State Tracking 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 tracks the global states (e.g., memory) of the interpreter.
10//
11//===----------------------------------------------------------------------===//
12
13#include "Context.h"
14#include "llvm/IR/GetElementPtrTypeIterator.h"
15#include "llvm/IR/Instructions.h"
16#include "llvm/Support/MathExtras.h"
17
18namespace llvm::ubi {
19
20Context::Context(Module &M, const AsmParserContext *ParserContext)
21 : Ctx(M.getContext()), M(M), ParserContext(ParserContext),
22 DL(M.getDataLayout()), TLIImpl(M.getTargetTriple()) {}
23
24Context::~Context() = default;
25
26bool Context::initGlobalValues() {
27 // Register all function and block targets that may be used by indirect calls
28 // and branches.
29 for (Function &F : M) {
30 if (F.hasAddressTaken(nullptr,
31 /*IgnoreCallbackUses=*/false,
32 /*IgnoreAssumeLikeCalls=*/false)) {
33 // TODO: Use precise alignment for function pointers if it is necessary.
34 auto FuncObj = allocate(Size: 0, Align: F.getPointerAlignment(DL).value(), Name: F.getName(),
35 AS: DL.getProgramAddressSpace(), InitKind: MemInitKind::Zeroed,
36 AllocKind: MemAllocKind::Global, /*IsIRGlobalValue=*/true);
37 if (!FuncObj)
38 return false;
39 ValidFuncTargets.try_emplace(Key: FuncObj->getAddress(),
40 Args: std::make_pair(x: &F, y&: FuncObj));
41 FuncAddrMap.try_emplace(Key: &F, Args: deriveFromMemoryObject(Obj: FuncObj));
42 }
43
44 for (BasicBlock &BB : F) {
45 if (!BB.hasAddressTaken())
46 continue;
47 auto BlockObj = allocate(Size: 0, Align: 1, Name: BB.getName(), AS: DL.getProgramAddressSpace(),
48 InitKind: MemInitKind::Zeroed, AllocKind: MemAllocKind::BlockAddress);
49 if (!BlockObj)
50 return false;
51 ValidBlockTargets.try_emplace(Key: BlockObj->getAddress(),
52 Args: std::make_pair(x: &BB, y&: BlockObj));
53 BlockAddrMap.try_emplace(Key: &BB, Args: deriveFromMemoryObject(Obj: BlockObj));
54 }
55 }
56
57 for (GlobalVariable &GV : M.globals()) {
58 Type *ValueTy = GV.getValueType();
59 const uint64_t Size = getEffectiveTypeAllocSize(Ty: ValueTy);
60 Align Alignment = GV.getPointerAlignment(DL);
61 auto InitKind =
62 GV.hasInitializer() ? MemInitKind::Zeroed : MemInitKind::Uninitialized;
63 const auto Obj =
64 allocate(Size, Align: Alignment.value(), Name: GV.getName(), AS: GV.getAddressSpace(),
65 InitKind, AllocKind: MemAllocKind::Global, /*IsIRGlobalValue=*/true);
66
67 if (!Obj)
68 return false;
69
70 Obj->setIsConstant(GV.isConstant());
71 GlobalAddrMap.try_emplace(Key: &GV, Args: deriveFromMemoryObject(Obj));
72 }
73
74 for (GlobalVariable &GV : M.globals()) {
75 if (!GV.hasInitializer())
76 continue;
77
78 MemoryObject *Obj = GlobalAddrMap.at(Val: &GV).provenance().getMemoryObject();
79 assert(Obj && "global pointer should have memory object provenance");
80
81 Constant *Init = GV.getInitializer();
82
83 const AnyValue *InitVal = getConstantValue(C: Init);
84 if (!InitVal)
85 return false;
86
87 store(MO&: *Obj, Offset: 0, Val: *InitVal, ValTy: GV.getValueType());
88 resetNoncacheableConstantBuffer();
89 }
90 return true;
91}
92
93MaterializedConstant Context::getConstantValueImpl(Constant *C) {
94 if (isa<PoisonValue>(Val: C))
95 return MaterializedConstant(AnyValue::getPoisonValue(Ctx&: *this, Ty: C->getType()),
96 /*Cacheable=*/true);
97
98 if (isa<UndefValue>(Val: C)) {
99 // We treat undef as a freshly freeze poison.
100 auto Value = AnyValue::getPoisonValue(Ctx&: *this, Ty: C->getType());
101 freeze(Val&: Value, Ty: C->getType());
102 return MaterializedConstant(std::move(Value), /*Cacheable=*/false);
103 }
104
105 if (isa<ConstantAggregateZero>(Val: C))
106 return MaterializedConstant(AnyValue::getNullValue(Ctx&: *this, Ty: C->getType()),
107 /*Cacheable=*/true);
108
109 if (isa<ConstantPointerNull>(Val: C))
110 return MaterializedConstant(AnyValue::getNullValue(Ctx&: *this, Ty: C->getType()),
111 /*Cacheable=*/true);
112
113 if (auto *CI = dyn_cast<ConstantInt>(Val: C)) {
114 if (auto *VecTy = dyn_cast<VectorType>(Val: CI->getType()))
115 return MaterializedConstant(
116 std::vector<AnyValue>(getEVL(EC: VecTy->getElementCount()),
117 AnyValue(CI->getValue())),
118 /*Cacheable=*/true);
119 return MaterializedConstant(CI->getValue(), /*Cacheable=*/true);
120 }
121
122 if (auto *CFP = dyn_cast<ConstantFP>(Val: C)) {
123 if (auto *VecTy = dyn_cast<VectorType>(Val: CFP->getType()))
124 return MaterializedConstant(
125 std::vector<AnyValue>(getEVL(EC: VecTy->getElementCount()),
126 AnyValue(CFP->getValue())),
127 /*Cacheable=*/true);
128 return MaterializedConstant(CFP->getValue(), /*Cacheable=*/true);
129 }
130
131 if (auto *CB = dyn_cast<ConstantByte>(Val: C)) {
132 if (auto *VecTy = dyn_cast<VectorType>(Val: CB->getType()))
133 return MaterializedConstant(
134 std::vector<AnyValue>(
135 getEVL(EC: VecTy->getElementCount()),
136 AnyValue(ByteValue(CB->getValue(), DL.isLittleEndian()))),
137 /*Cacheable=*/true);
138 return MaterializedConstant(ByteValue(CB->getValue(), DL.isLittleEndian()),
139 /*Cacheable=*/true);
140 }
141
142 if (auto *CDS = dyn_cast<ConstantDataSequential>(Val: C)) {
143 std::vector<AnyValue> Elts;
144 Elts.reserve(n: CDS->getNumElements());
145 bool Cacheable = true;
146 for (uint32_t I = 0, E = CDS->getNumElements(); I != E; ++I) {
147 auto Elt = getConstantValue(C: CDS->getElementAsConstant(i: I));
148 if (!Elt)
149 return std::nullopt;
150 Cacheable &= Elt->isCacheable();
151 Elts.push_back(x: *Elt);
152 }
153 return MaterializedConstant(std::move(Elts), Cacheable);
154 }
155
156 if (auto *CA = dyn_cast<ConstantAggregate>(Val: C)) {
157 std::vector<AnyValue> Elts;
158 Elts.reserve(n: CA->getNumOperands());
159 bool Cacheable = true;
160 for (uint32_t I = 0, E = CA->getNumOperands(); I != E; ++I) {
161 auto Elt = getConstantValue(C: CA->getOperand(i_nocapture: I));
162 if (!Elt)
163 return std::nullopt;
164 Cacheable &= Elt->isCacheable();
165 Elts.push_back(x: *Elt);
166 }
167 return MaterializedConstant(std::move(Elts), Cacheable);
168 }
169
170 if (auto *BA = dyn_cast<BlockAddress>(Val: C))
171 return MaterializedConstant(BlockAddrMap.at(Val: BA->getBasicBlock()),
172 /*Cacheable=*/true);
173
174 if (auto *GV = dyn_cast<GlobalVariable>(Val: C))
175 return MaterializedConstant(GlobalAddrMap.at(Val: GV), /*Cacheable=*/true);
176
177 if (auto *F = dyn_cast<Function>(Val: C))
178 return MaterializedConstant(FuncAddrMap.at(Val: F), /*Cacheable=*/true);
179
180 if (auto *CE = dyn_cast<ConstantExpr>(Val: C))
181 return evaluateConstantExpression(CE);
182
183 return std::nullopt;
184}
185
186MaterializedConstant Context::evaluateConstantExpression(ConstantExpr *CE) {
187 unsigned Opc = CE->getOpcode();
188 switch (Opc) {
189 case Instruction::Trunc: {
190 const auto *Src = getConstantValue(C: CE->getOperand(i_nocapture: 0));
191 if (!Src)
192 return std::nullopt;
193 if (Src->isPoison())
194 return MaterializedConstant(AnyValue::poison(), Src->isCacheable());
195 unsigned BitWidth = CE->getType()->getScalarSizeInBits();
196 if (Src->isInteger())
197 return MaterializedConstant(Src->asInteger().trunc(width: BitWidth),
198 Src->isCacheable());
199 std::vector<AnyValue> Vec = Src->asAggregate();
200 for (auto &V : Vec) {
201 if (V.isInteger())
202 V = V.asInteger().trunc(width: BitWidth);
203 }
204 return MaterializedConstant(std::move(Vec), Src->isCacheable());
205 }
206 case Instruction::BitCast: {
207 Constant *SrcOp = CE->getOperand(i_nocapture: 0);
208 const auto *Src = getConstantValue(C: SrcOp);
209 if (!Src)
210 return std::nullopt;
211 SmallVector<Byte> Bytes;
212 Bytes.resize(N: getEffectiveTypeStoreSize(Ty: CE->getType()), NV: Byte::concrete(Val: 0));
213 toBytes(Val: *Src, Ty: SrcOp->getType(), Bytes);
214 return MaterializedConstant(fromBytes(Bytes, Ty: CE->getType()),
215 Src->isCacheable());
216 }
217 case Instruction::InsertElement: {
218 const auto *Src = getConstantValue(C: CE->getOperand(i_nocapture: 0));
219 if (!Src)
220 return std::nullopt;
221 const auto *Val = getConstantValue(C: CE->getOperand(i_nocapture: 1));
222 if (!Val)
223 return std::nullopt;
224 const auto *Idx = getConstantValue(C: CE->getOperand(i_nocapture: 2));
225 if (!Idx)
226 return std::nullopt;
227 auto &SrcVec = Src->asAggregate();
228 bool Cacheable =
229 Src->isCacheable() && Val->isCacheable() && Idx->isCacheable();
230 if (Idx->isPoison() || Idx->asInteger().uge(RHS: SrcVec.size()))
231 return MaterializedConstant(
232 AnyValue::getPoisonValue(Ctx&: *this, Ty: CE->getType()), Cacheable);
233 std::vector<AnyValue> ResVec = SrcVec;
234 ResVec[Idx->asInteger().getZExtValue()] = *Val;
235 return MaterializedConstant(std::move(ResVec), Cacheable);
236 }
237 case Instruction::ExtractElement: {
238 const auto *Src = getConstantValue(C: CE->getOperand(i_nocapture: 0));
239 if (!Src)
240 return std::nullopt;
241 const auto *Idx = getConstantValue(C: CE->getOperand(i_nocapture: 1));
242 if (!Idx)
243 return std::nullopt;
244 auto &SrcVec = Src->asAggregate();
245 bool Cacheable = Src->isCacheable() && Idx->isCacheable();
246 if (Idx->isPoison() || Idx->asInteger().uge(RHS: SrcVec.size()))
247 return MaterializedConstant(
248 AnyValue::getPoisonValue(Ctx&: *this, Ty: CE->getType()), Cacheable);
249 return MaterializedConstant(SrcVec[Idx->asInteger().getZExtValue()],
250 Cacheable);
251 }
252 case Instruction::ShuffleVector: {
253 const auto *LHS = getConstantValue(C: CE->getOperand(i_nocapture: 0));
254 if (!LHS)
255 return std::nullopt;
256 const auto *RHS = getConstantValue(C: CE->getOperand(i_nocapture: 1));
257 if (!RHS)
258 return std::nullopt;
259 auto &LHSVec = LHS->asAggregate();
260 auto &RHSVec = RHS->asAggregate();
261 uint32_t Size = cast<VectorType>(Val: CE->getOperand(i_nocapture: 0)->getType())
262 ->getElementCount()
263 .getKnownMinValue();
264 std::vector<AnyValue> Res;
265 uint32_t DstLen =
266 getEVL(EC: cast<VectorType>(Val: CE->getType())->getElementCount());
267 Res.reserve(n: DstLen);
268 uint32_t Stride = CE->getShuffleMask().size();
269 // For scalable vectors, we need to repeat the shuffle mask until we fill
270 // the destination vector.
271 for (uint32_t Off = 0; Off != DstLen; Off += Stride) {
272 for (int Idx : CE->getShuffleMask()) {
273 if (Idx == PoisonMaskElem)
274 Res.push_back(
275 x: AnyValue::getPoisonValue(Ctx&: *this, Ty: CE->getType()->getScalarType()));
276 else if (Idx < static_cast<int>(Size))
277 Res.push_back(x: LHSVec[Idx]);
278 else
279 Res.push_back(x: RHSVec[Idx - Size]);
280 }
281 }
282 return MaterializedConstant(std::move(Res),
283 LHS->isCacheable() && RHS->isCacheable());
284 }
285 case Instruction::GetElementPtr: {
286 // Temporary variable for reference to poison values when the subexpression
287 // cannot be evaluated. As the reference will be consumed immediately, we
288 // don't need to store them into a list.
289 AnyValue PoisonValue;
290 bool Cacheable = true;
291 AnyValue Res =
292 computeGEP(GEP&: *cast<GEPOperator>(Val: CE), GetValue: [&](Value *V) -> const AnyValue & {
293 const auto *Val = getConstantValue(C: cast<Constant>(Val: V));
294 if (Val) {
295 Cacheable &= Val->isCacheable();
296 return *Val;
297 }
298 PoisonValue = AnyValue::getPoisonValue(Ctx&: *this, Ty: V->getType());
299 return PoisonValue;
300 });
301 if (!PoisonValue.isNone())
302 return std::nullopt;
303 return MaterializedConstant(std::move(Res), Cacheable);
304 }
305 case Instruction::PtrToAddr:
306 case Instruction::PtrToInt: {
307 const auto *Src = getConstantValue(C: CE->getOperand(i_nocapture: 0));
308 if (!Src)
309 return std::nullopt;
310 bool Cacheable = Opc == Instruction::PtrToAddr && Src->isCacheable();
311 if (Src->isPoison())
312 return MaterializedConstant(AnyValue::poison(), Cacheable);
313 unsigned BitWidth = CE->getType()->getScalarSizeInBits();
314 if (Src->isPointer()) {
315 if (Opc == Instruction::PtrToInt)
316 exposeProvenance(Prov&: Src->asPointer().provenance());
317 return MaterializedConstant(
318 Src->asPointer().address().zextOrTrunc(width: BitWidth), Cacheable);
319 }
320 std::vector<AnyValue> Vec = Src->asAggregate();
321 for (auto &V : Vec) {
322 if (V.isPointer()) {
323 if (Opc == Instruction::PtrToInt)
324 exposeProvenance(Prov&: V.asPointer().provenance());
325 V = V.asPointer().address().zextOrTrunc(width: BitWidth);
326 }
327 }
328 return MaterializedConstant(std::move(Vec), Cacheable);
329 }
330 case Instruction::IntToPtr: {
331 const auto *Src = getConstantValue(C: CE->getOperand(i_nocapture: 0));
332 if (!Src)
333 return std::nullopt;
334 if (Src->isPoison())
335 return MaterializedConstant(AnyValue::poison(), /*Cacheable=*/false);
336 unsigned BitWidth =
337 DL.getPointerSizeInBits(AS: CE->getType()->getPointerAddressSpace());
338 if (Src->isInteger())
339 return MaterializedConstant(
340 Pointer(getWildcardProvenance(),
341 Src->asInteger().zextOrTrunc(width: BitWidth)),
342 /*Cacheable=*/false);
343 std::vector<AnyValue> Vec = Src->asAggregate();
344 for (auto &V : Vec) {
345 if (V.isInteger())
346 V = Pointer(getWildcardProvenance(),
347 V.asInteger().zextOrTrunc(width: BitWidth));
348 }
349 return MaterializedConstant(std::move(Vec), /*Cacheable=*/false);
350 }
351 case Instruction::AddrSpaceCast:
352 return std::nullopt;
353 default:
354 assert(Instruction::isBinaryOp(Opc) && "Must be binary operator?");
355 const auto *LHS = getConstantValue(C: CE->getOperand(i_nocapture: 0));
356 if (!LHS)
357 return std::nullopt;
358 const auto *RHS = getConstantValue(C: CE->getOperand(i_nocapture: 1));
359 if (!RHS)
360 return std::nullopt;
361
362 bool HasNUW = false;
363 bool HasNSW = false;
364 if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(Val: CE)) {
365 HasNUW = OBO->hasNoUnsignedWrap();
366 HasNSW = OBO->hasNoSignedWrap();
367 }
368
369 auto ScalarEval = [&](const AnyValue &LHS,
370 const AnyValue &RHS) -> AnyValue {
371 if (LHS.isPoison() || RHS.isPoison())
372 return AnyValue::poison();
373 auto &LHSVal = LHS.asInteger();
374 auto &RHSVal = RHS.asInteger();
375 switch (Opc) {
376 case Instruction::Add:
377 return addNoWrap(LHS: LHSVal, RHS: RHSVal, HasNSW, HasNUW);
378 case Instruction::Sub:
379 return subNoWrap(LHS: LHSVal, RHS: RHSVal, HasNSW, HasNUW);
380 case Instruction::Xor:
381 return LHSVal ^ RHSVal;
382 default:
383 llvm_unreachable("Unsupported opcode in constant expression.");
384 }
385 };
386
387 bool Cacheable = LHS->isCacheable() && RHS->isCacheable();
388
389 if (CE->getType()->isVectorTy()) {
390 auto &LHSVec = LHS->asAggregate();
391 auto &RHSVec = RHS->asAggregate();
392 std::vector<AnyValue> ResVec;
393 ResVec.reserve(n: LHSVec.size());
394 for (const auto &[ScalarLHS, ScalarRHS] : zip(t: LHSVec, u: RHSVec))
395 ResVec.push_back(x: ScalarEval(ScalarLHS, ScalarRHS));
396 return MaterializedConstant(std::move(ResVec), Cacheable);
397 }
398
399 return MaterializedConstant(ScalarEval(*LHS, *RHS), Cacheable);
400 }
401}
402
403const MaterializedConstant *Context::getConstantValue(Constant *C) {
404 auto It = ConstCache.find(x: C);
405 if (It != ConstCache.end())
406 return &It->second;
407
408 MaterializedConstant Val = getConstantValueImpl(C);
409 if (Val.isNone())
410 return nullptr;
411 if (!Val.isCacheable()) {
412 assert(NoncacheableConstCount <= 1024 && "Unbounded temporary buffer.");
413 ++NoncacheableConstCount;
414 return new (NoncacheableConstBuffer.Allocate())
415 MaterializedConstant(std::move(Val));
416 }
417
418 return &ConstCache.emplace(args&: C, args: std::move(Val)).first->second;
419}
420
421void Context::resetNoncacheableConstantBuffer() {
422 NoncacheableConstBuffer.DestroyAll();
423 NoncacheableConstCount = 0;
424}
425
426APInt Context::getTag(uint32_t BitWidth, Provenance &Prov) {
427 // Nullary provenance.
428 if (!Prov.getMemoryObject())
429 return APInt::getZero(numBits: BitWidth);
430 // The tag is already initialized.
431 if (!Prov.getTag().isZero())
432 return Prov.getTag();
433
434 // FIXME: This doesn't work when the address space is too small.
435 while (true) {
436 APInt Tag = generateRandomAPInt(BitWidth);
437 if (Tag.isZero() || !TaggedProvenances.try_emplace(Key: Tag, Args: &Prov).second)
438 continue;
439 Prov.setTag(Tag);
440 Prov.getMemoryObject()->AssociatedTags.push_back(Elt: Tag);
441 return Tag;
442 }
443}
444
445AnyValue Context::fromBytes(ConstBytesView Bytes, Type *Ty,
446 uint32_t OffsetInBits, bool CheckPaddingBits,
447 bool *ContainsUndefinedBits) {
448 uint32_t NumBits = DL.getTypeSizeInBits(Ty).getFixedValue();
449 uint32_t NewOffsetInBits = OffsetInBits + NumBits;
450 if (CheckPaddingBits)
451 NewOffsetInBits = alignTo(Value: NewOffsetInBits, Align: 8);
452 bool NeedsPadding = NewOffsetInBits != OffsetInBits + NumBits;
453 uint32_t NumBitsToExtract = NewOffsetInBits - OffsetInBits;
454 uint32_t NumWords = APInt::getNumWords(BitWidth: NumBitsToExtract);
455 constexpr uint32_t WordBits = APInt::APINT_BITS_PER_WORD;
456 SmallVector<APInt::WordType> RawBits;
457 bool IsByteType = Ty->isByteTy();
458 // LogicalBytes is always little-endian.
459 std::vector<Byte> LogicalBytes;
460 if (IsByteType)
461 LogicalBytes.resize(new_size: divideCeil(Numerator: NumBitsToExtract, Denominator: 8));
462 else
463 RawBits.resize(N: NumWords);
464 bool IsTagValid = Ty->isPointerTy();
465 SmallVector<APInt::WordType> RawTagBits;
466 if (Ty->isPointerTy())
467 RawTagBits.resize(N: NumWords);
468 for (uint32_t I = 0; I < NumBitsToExtract; I += 8) {
469 // Try to form a 'logical' byte that represents the bits in the range
470 // [BitsStart, BitsEnd].
471 uint32_t NumBitsInByte = std::min(a: 8U, b: NumBitsToExtract - I);
472 uint32_t BitsStart = OffsetInBits + I;
473 uint32_t BitsEnd = BitsStart + NumBitsInByte - 1;
474 Byte LogicalByte;
475 // Check whether it is a cross-byte access.
476 if (((BitsStart ^ BitsEnd) & ~7) == 0)
477 LogicalByte = Bytes[BitsStart / 8].lshr(Shift: BitsStart % 8);
478 else
479 LogicalByte =
480 Byte::fshr(Low: Bytes[BitsStart / 8], High: Bytes[BitsEnd / 8], ShAmt: BitsStart % 8);
481
482 uint32_t Mask = (1U << NumBitsInByte) - 1;
483 // If any of the bits in the byte is poison, the whole value is poison.
484 if (!IsByteType &&
485 (~LogicalByte.ConcreteMask & ~LogicalByte.Value & Mask)) {
486 if (ContainsUndefinedBits)
487 *ContainsUndefinedBits = true;
488 OffsetInBits = NewOffsetInBits;
489 return AnyValue::poison();
490 }
491 uint8_t RandomBits = 0;
492 if (~LogicalByte.ConcreteMask & Mask) {
493 // This byte contains undef bits.
494 if (ContainsUndefinedBits)
495 *ContainsUndefinedBits = true;
496
497 if (!IsByteType && getEffectiveUndefValueBehavior() ==
498 UndefValueBehavior::NonDeterministic) {
499 // We don't use std::uniform_int_distribution here because it produces
500 // different results across different library implementations. Instead,
501 // we directly use the low bits from Rng.
502 RandomBits = static_cast<uint8_t>(Rng());
503 }
504 }
505
506 if (IsByteType) {
507 // FIXME: Currently we treat undef bits as poison bits in the byte value,
508 // because keeping undef bits reintroduces undef SSA values.
509 // It should be fixed by completely removing undef bits from the memory.
510 LogicalByte.poisonBits(Mask: ~LogicalByte.ConcreteMask);
511 LogicalBytes[I / 8] = LogicalByte;
512 continue;
513 }
514
515 uint8_t ActualBits = ((LogicalByte.Value & LogicalByte.ConcreteMask) |
516 (RandomBits & ~LogicalByte.ConcreteMask)) &
517 Mask;
518 RawBits[I / WordBits] |= static_cast<APInt::WordType>(ActualBits)
519 << (I % WordBits);
520 if (IsTagValid) {
521 assert((LogicalByte.TagMask & LogicalByte.ConcreteMask) ==
522 LogicalByte.TagMask);
523 if ((LogicalByte.TagMask & Mask) == Mask) {
524 uint8_t ActualTagBits = LogicalByte.TagValue & Mask;
525 RawTagBits[I / WordBits] |= static_cast<APInt::WordType>(ActualTagBits)
526 << (I % WordBits);
527 } else {
528 IsTagValid = false;
529 }
530 }
531 }
532
533 OffsetInBits = NewOffsetInBits;
534
535 if (IsByteType) {
536 assert(!CheckPaddingBits &&
537 "Non-vector-element cases should be handled by the fast path.");
538 if (NumBits & 7) {
539 uint8_t Mask = static_cast<uint8_t>((~0U) << (NumBits & 7));
540 LogicalBytes.back().zeroBits(Mask);
541 }
542 if (DL.isBigEndian())
543 std::reverse(first: LogicalBytes.begin(), last: LogicalBytes.end());
544 return ByteValue(NumBits, std::move(LogicalBytes), DL.isLittleEndian());
545 }
546
547 APInt Bits(NumBitsToExtract, RawBits);
548
549 // Padding bits for non-byte-sized scalar types must be zero.
550 if (NeedsPadding) {
551 if (!Bits.isIntN(N: NumBits)) {
552 if (ContainsUndefinedBits)
553 *ContainsUndefinedBits = true;
554 return AnyValue::poison();
555 }
556 Bits = Bits.trunc(width: NumBits);
557 }
558
559 if (Ty->isIntegerTy())
560 return Bits;
561 if (Ty->isFloatingPointTy())
562 return APFloat(Ty->getFltSemantics(), Bits);
563 assert(Ty->isPointerTy() && "Expect a pointer type");
564 // Try to recover provenance from the tag.
565 if (IsTagValid) {
566 APInt Tag(NumBits, RawTagBits);
567 if (auto Prov = TaggedProvenances.lookup(Val: Tag))
568 return Pointer(std::move(Prov), Bits);
569 }
570 return Pointer(Bits);
571}
572
573AnyValue Context::fromBytes(ArrayRef<Byte> Bytes, Type *Ty,
574 bool *ContainsUndefinedBits) {
575 assert(Bytes.size() == getEffectiveTypeStoreSize(Ty) &&
576 "Invalid byte array size for the type");
577 if (Ty->isIntegerTy() || Ty->isFloatingPointTy() || Ty->isPointerTy())
578 return fromBytes(Bytes: ConstBytesView(Bytes, DL), Ty, /*OffsetInBits=*/0,
579 /*CheckPaddingBits=*/true, ContainsUndefinedBits);
580 if (Ty->isByteTy()) {
581 unsigned BitWidth = Ty->getByteBitWidth();
582 if (BitWidth & 7) {
583 if (!(DL.isLittleEndian() ? Bytes.back() : Bytes.front())
584 .areHighBitsZExtd(BitsFrom: BitWidth & 7)) {
585 if (ContainsUndefinedBits)
586 *ContainsUndefinedBits = true;
587 return ByteValue::poison(BitWidth, IsLittleEndian: DL.isLittleEndian());
588 }
589 }
590 ByteValue Res(BitWidth, Bytes, DL.isLittleEndian());
591 bool HasUndefinedBits = false;
592 for (Byte &V : Res.mutableBytes()) {
593 if (V.ConcreteMask != 255)
594 HasUndefinedBits = true;
595 V.poisonBits(Mask: ~V.ConcreteMask);
596 }
597 if (ContainsUndefinedBits)
598 *ContainsUndefinedBits = HasUndefinedBits;
599 return AnyValue(std::move(Res));
600 }
601
602 if (auto *VecTy = dyn_cast<VectorType>(Val: Ty)) {
603 Type *ElemTy = VecTy->getElementType();
604 uint32_t ElemBits = DL.getTypeSizeInBits(Ty: ElemTy).getFixedValue();
605 uint32_t NumElements = getEVL(EC: VecTy->getElementCount());
606 // Check padding bits. <N x iM> acts as if an integer type with N * M bits.
607 uint32_t VecBits = ElemBits * NumElements;
608 uint32_t AlignedVecBits = alignTo(Value: VecBits, Align: 8);
609 ConstBytesView View(Bytes, DL);
610 if (VecBits != AlignedVecBits) {
611 const Byte &PaddingByte = View[Bytes.size() - 1];
612 uint32_t Mask = (~0U << (VecBits % 8)) & 255U;
613 // Make sure all high padding bits are zero.
614 if ((PaddingByte.ConcreteMask & ~PaddingByte.Value & Mask) != Mask) {
615 if (ContainsUndefinedBits)
616 *ContainsUndefinedBits = true;
617 return AnyValue::getPoisonValue(Ctx&: *this, Ty);
618 }
619 }
620
621 std::vector<AnyValue> ValVec;
622 ValVec.reserve(n: NumElements);
623 // For little endian element zero is put in the least significant bits of
624 // the integer, and for big endian element zero is put in the most
625 // significant bits.
626 for (uint32_t I = 0; I != NumElements; ++I)
627 ValVec.push_back(
628 x: fromBytes(Bytes: View, Ty: ElemTy,
629 OffsetInBits: DL.isLittleEndian() ? I * ElemBits
630 : VecBits - ElemBits - I * ElemBits,
631 /*CheckPaddingBits=*/false, ContainsUndefinedBits));
632 return AnyValue(std::move(ValVec));
633 }
634 if (auto *ArrTy = dyn_cast<ArrayType>(Val: Ty)) {
635 Type *ElemTy = ArrTy->getElementType();
636 uint64_t Stride = getEffectiveTypeAllocSize(Ty: ElemTy);
637 uint64_t StoreSize = getEffectiveTypeStoreSize(Ty: ElemTy);
638 uint32_t NumElements = ArrTy->getNumElements();
639 std::vector<AnyValue> ValVec;
640 ValVec.reserve(n: NumElements);
641 for (uint32_t I = 0; I != NumElements; ++I)
642 ValVec.push_back(x: fromBytes(Bytes: Bytes.slice(N: I * Stride, M: StoreSize), Ty: ElemTy,
643 ContainsUndefinedBits));
644 return AnyValue(std::move(ValVec));
645 }
646 if (auto *StructTy = dyn_cast<StructType>(Val: Ty)) {
647 const StructLayout *Layout = DL.getStructLayout(Ty: StructTy);
648 std::vector<AnyValue> ValVec;
649 uint32_t NumElements = StructTy->getNumElements();
650 ValVec.reserve(n: NumElements);
651 for (uint32_t I = 0; I != NumElements; ++I) {
652 Type *ElemTy = StructTy->getElementType(N: I);
653 ValVec.push_back(x: fromBytes(
654 Bytes: Bytes.slice(N: getEffectiveTypeSize(Size: Layout->getElementOffset(Idx: I)),
655 M: getEffectiveTypeStoreSize(Ty: ElemTy)),
656 Ty: ElemTy, ContainsUndefinedBits));
657 }
658 return AnyValue(std::move(ValVec));
659 }
660 llvm_unreachable("Unsupported first class type.");
661}
662
663void Context::toBytes(const AnyValue &Val, Type *Ty, uint32_t OffsetInBits,
664 MutableBytesView Bytes, bool PaddingBits) {
665 uint32_t NumBits = DL.getTypeSizeInBits(Ty).getFixedValue();
666 uint32_t NewOffsetInBits = OffsetInBits + NumBits;
667 if (PaddingBits)
668 NewOffsetInBits = alignTo(Value: NewOffsetInBits, Align: 8);
669 bool NeedsPadding = NewOffsetInBits != OffsetInBits + NumBits;
670 auto WriteBits = [&](const APInt &Bits, const APInt *TagBits) {
671 for (uint32_t I = 0, E = Bits.getBitWidth(); I < E; I += 8) {
672 uint32_t NumBitsInByte = std::min(a: 8U, b: E - I);
673 uint32_t BitsStart = OffsetInBits + I;
674 uint32_t BitsEnd = BitsStart + NumBitsInByte - 1;
675 uint8_t BitsVal =
676 static_cast<uint8_t>(Bits.extractBitsAsZExtValue(numBits: NumBitsInByte, bitPosition: I));
677
678 Bytes[BitsStart / 8].writeBits(
679 Mask: static_cast<uint8_t>(((1U << NumBitsInByte) - 1) << (BitsStart % 8)),
680 Val: static_cast<uint8_t>(BitsVal << (BitsStart % 8)));
681 // If it is a cross-byte access, write the remaining bits to the next
682 // byte.
683 if (((BitsStart ^ BitsEnd) & ~7) != 0)
684 Bytes[BitsEnd / 8].writeBits(
685 Mask: static_cast<uint8_t>((1U << (BitsEnd % 8 + 1)) - 1),
686 Val: static_cast<uint8_t>(BitsVal >> (8 - (BitsStart % 8))));
687
688 if (TagBits) {
689 uint8_t TagBitsVal = static_cast<uint8_t>(
690 TagBits->extractBitsAsZExtValue(numBits: NumBitsInByte, bitPosition: I));
691 Bytes[BitsStart / 8].writeTagBits(
692 Mask: static_cast<uint8_t>(((1U << NumBitsInByte) - 1)
693 << (BitsStart % 8)),
694 Tag: static_cast<uint8_t>(TagBitsVal << (BitsStart % 8)));
695 // If it is a cross-byte access, write the remaining bits to the next
696 // byte.
697 if (((BitsStart ^ BitsEnd) & ~7) != 0)
698 Bytes[BitsEnd / 8].writeTagBits(
699 Mask: static_cast<uint8_t>((1U << (BitsEnd % 8 + 1)) - 1),
700 Tag: static_cast<uint8_t>(TagBitsVal >> (8 - (BitsStart % 8))));
701 }
702 }
703 };
704 if (Val.isPoison()) {
705 for (uint32_t I = 0, E = NewOffsetInBits - OffsetInBits; I < E;) {
706 uint32_t BitsStart = OffsetInBits + I;
707 uint32_t NumBitsInByte = std::min(a: 8 - BitsStart % 8, b: E - I);
708 assert(((BitsStart ^ (BitsStart + NumBitsInByte - 1)) & ~7) == 0 &&
709 "Across byte boundary.");
710 Bytes[BitsStart / 8].poisonBits(
711 Mask: static_cast<uint8_t>(((1U << NumBitsInByte) - 1) << (BitsStart % 8)));
712 I += NumBitsInByte;
713 }
714 } else if (Ty->isIntegerTy()) {
715 auto &Bits = Val.asInteger();
716 WriteBits(NeedsPadding ? Bits.zext(width: NewOffsetInBits - OffsetInBits) : Bits,
717 /*TagBits=*/nullptr);
718 } else if (Ty->isFloatingPointTy()) {
719 auto Bits = Val.asFloat().bitcastToAPInt();
720 WriteBits(NeedsPadding ? Bits.zext(width: NewOffsetInBits - OffsetInBits) : Bits,
721 /*TagBits=*/nullptr);
722 } else if (Ty->isPointerTy()) {
723 auto &AddressBits = Val.asPointer().address();
724 APInt Tag = getTag(BitWidth: AddressBits.getBitWidth(), Prov&: Val.asPointer().provenance());
725 if (NeedsPadding)
726 Tag = Tag.zext(width: NewOffsetInBits - OffsetInBits);
727 WriteBits(NeedsPadding ? AddressBits.zext(width: NewOffsetInBits - OffsetInBits)
728 : AddressBits,
729 &Tag);
730 } else if (Ty->isByteTy()) {
731 assert(!PaddingBits &&
732 "Non-vector-element cases should be handled by the fast path.");
733 auto &ByteVal = Val.asByte();
734 ConstBytesView SrcBytes(ByteVal.bytes(), DL);
735 for (uint32_t I = 0, E = static_cast<uint32_t>(SrcBytes.size()); I != E;
736 ++I) {
737 uint32_t NumBitsInByte = std::min(a: 8U, b: NumBits - I * 8);
738 uint32_t BitsStart = OffsetInBits + I * 8;
739 uint32_t BitsEnd = BitsStart + NumBitsInByte - 1;
740
741 Bytes[BitsStart / 8].writeByte(
742 Mask: static_cast<uint8_t>(((1U << NumBitsInByte) - 1) << (BitsStart % 8)),
743 RHS: SrcBytes[I].shl(Shift: BitsStart % 8));
744 // If it is a cross-byte access, write the remaining bits to the next
745 // byte.
746 if (((BitsStart ^ BitsEnd) & ~7) != 0)
747 Bytes[BitsEnd / 8].writeByte(
748 Mask: static_cast<uint8_t>((1U << (BitsEnd % 8 + 1)) - 1),
749 RHS: SrcBytes[I].lshr(Shift: 8 - (BitsStart % 8)));
750 }
751 } else {
752 llvm_unreachable("Unsupported scalar type.");
753 }
754}
755
756void Context::toBytes(const AnyValue &Val, Type *Ty,
757 MutableArrayRef<Byte> Bytes) {
758 assert(Bytes.size() == getEffectiveTypeStoreSize(Ty) &&
759 "Invalid byte array size for the type");
760 if (Ty->isIntegerTy() || Ty->isFloatingPointTy() || Ty->isPointerTy()) {
761 toBytes(Val, Ty, /*OffsetInBits=*/0, Bytes: MutableBytesView(Bytes, DL),
762 /*PaddingBits=*/true);
763 return;
764 }
765 if (Ty->isByteTy()) {
766 auto &ByteVal = Val.asByte();
767 ArrayRef<Byte> SrcBytes = ByteVal.bytes();
768 assert(Bytes.size() == SrcBytes.size() && "Mismatched byte array.");
769 copy(Range&: SrcBytes, Out: Bytes.begin());
770 return;
771 }
772
773 if (auto *VecTy = dyn_cast<VectorType>(Val: Ty)) {
774 Type *ElemTy = VecTy->getElementType();
775 uint32_t ElemBits = DL.getTypeSizeInBits(Ty: ElemTy).getFixedValue();
776 uint32_t NumElements = getEVL(EC: VecTy->getElementCount());
777 // Zero padding bits. <N x iM> acts as if an integer type with N * M bits.
778 uint32_t VecBits = ElemBits * NumElements;
779 uint32_t AlignedVecBits = alignTo(Value: VecBits, Align: 8);
780 MutableBytesView View(Bytes, DL);
781 if (VecBits != AlignedVecBits) {
782 Byte &PaddingByte = View[Bytes.size() - 1];
783 uint32_t Mask = (~0U << (VecBits % 8)) & 255U;
784 PaddingByte.zeroBits(Mask);
785 }
786 // For little endian element zero is put in the least significant bits of
787 // the integer, and for big endian element zero is put in the most
788 // significant bits.
789 if (DL.isLittleEndian()) {
790 for (const auto &[I, Val] : enumerate(First: Val.asAggregate()))
791 toBytes(Val, Ty: ElemTy, OffsetInBits: ElemBits * I, Bytes: View, /*PaddingBits=*/false);
792 } else {
793 for (const auto &[I, Val] : enumerate(First: reverse(C: Val.asAggregate())))
794 toBytes(Val, Ty: ElemTy, OffsetInBits: ElemBits * I, Bytes: View, /*PaddingBits=*/false);
795 }
796 return;
797 }
798
799 // Fill padding bytes due to alignment requirement.
800 auto FillUndefBytes = [&](uint64_t Begin, uint64_t End) {
801 fill(Range: Bytes.slice(N: Begin, M: End - Begin), Value: Byte::undef());
802 };
803 if (auto *ArrTy = dyn_cast<ArrayType>(Val: Ty)) {
804 Type *ElemTy = ArrTy->getElementType();
805 uint64_t Offset = 0;
806 uint64_t Stride = getEffectiveTypeAllocSize(Ty: ElemTy);
807 uint64_t StoreSize = getEffectiveTypeStoreSize(Ty: ElemTy);
808 for (const auto &SubVal : Val.asAggregate()) {
809 toBytes(Val: SubVal, Ty: ElemTy, Bytes: Bytes.slice(N: Offset, M: StoreSize));
810 FillUndefBytes(Offset + StoreSize, Offset + Stride);
811 Offset += Stride;
812 }
813 return;
814 }
815 if (auto *StructTy = dyn_cast<StructType>(Val: Ty)) {
816 const StructLayout *Layout = DL.getStructLayout(Ty: StructTy);
817 uint64_t LastAccessedOffset = 0;
818 for (uint32_t I = 0, E = Val.asAggregate().size(); I != E; ++I) {
819 Type *ElemTy = StructTy->getElementType(N: I);
820 uint64_t ElemOffset = getEffectiveTypeSize(Size: Layout->getElementOffset(Idx: I));
821 uint64_t ElemStoreSize = getEffectiveTypeStoreSize(Ty: ElemTy);
822 FillUndefBytes(LastAccessedOffset, ElemOffset);
823 toBytes(Val: Val.asAggregate()[I], Ty: ElemTy,
824 Bytes: Bytes.slice(N: ElemOffset, M: ElemStoreSize));
825 LastAccessedOffset = ElemOffset + ElemStoreSize;
826 }
827 FillUndefBytes(LastAccessedOffset, getEffectiveTypeStoreSize(Ty: StructTy));
828 return;
829 }
830
831 llvm_unreachable("Unsupported first class type.");
832}
833
834AnyValue Context::extractBits(const ByteValue &Src, uint32_t OffsetInBits,
835 Type *Ty) {
836 assert(OffsetInBits + DL.getTypeSizeInBits(Ty).getFixedValue() <=
837 Src.getBitWidth() &&
838 "Bit range out of bounds");
839 return fromBytes(Bytes: ConstBytesView(Src.bytes(), DL), Ty, OffsetInBits,
840 /*CheckPaddingBits=*/false,
841 /*ContainsUndefinedBits=*/nullptr);
842}
843
844void Context::insertBits(ByteValue &Base, uint32_t OffsetInBits,
845 const AnyValue &Val, Type *Ty) {
846 assert(OffsetInBits + DL.getTypeSizeInBits(Ty).getFixedValue() <=
847 Base.getBitWidth() &&
848 "Bit range out of bounds");
849 toBytes(Val, Ty, OffsetInBits, Bytes: MutableBytesView(Base.mutableBytes(), DL),
850 /*PaddingBits=*/false);
851}
852
853AnyValue Context::load(MemoryObject &MO, uint64_t Offset, Type *ValTy,
854 bool *ContainsUndefinedBits) {
855 return fromBytes(
856 Bytes: MO.getBytes().slice(N: Offset, M: getEffectiveTypeStoreSize(Ty: ValTy)), Ty: ValTy,
857 ContainsUndefinedBits);
858}
859
860void Context::store(MemoryObject &MO, uint64_t Offset, const AnyValue &Val,
861 Type *ValTy) {
862 toBytes(Val, Ty: ValTy,
863 Bytes: MO.getBytes().slice(N: Offset, M: getEffectiveTypeStoreSize(Ty: ValTy)));
864}
865
866void Context::storeRawBytes(MemoryObject &MO, uint64_t Offset, const void *Data,
867 uint64_t Size) {
868 for (uint64_t I = 0; I != Size; ++I)
869 MO[Offset + I] = Byte::concrete(Val: static_cast<const uint8_t *>(Data)[I]);
870}
871
872APInt Context::generateRandomAPInt(uint32_t BitWidth) {
873 SmallVector<APInt::WordType> RandomWords;
874 uint32_t NumWords = APInt::getNumWords(BitWidth);
875 RandomWords.reserve(N: NumWords);
876 static_assert(decltype(Rng)::word_size >=
877 std::numeric_limits<APInt::WordType>::digits,
878 "Unexpected Rng result type.");
879 for (uint32_t I = 0; I != NumWords; ++I)
880 RandomWords.push_back(Elt: static_cast<APInt::WordType>(Rng()));
881 return APInt(BitWidth, RandomWords);
882}
883
884void Context::freeze(AnyValue &Val, Type *Ty) {
885 if (Val.isPoison()) {
886 uint32_t Bits = DL.getTypeSizeInBits(Ty);
887 APInt RandomVal = mayUseNonDeterminism() ? generateRandomAPInt(BitWidth: Bits)
888 : APInt::getZero(numBits: Bits);
889 if (Ty->isIntegerTy())
890 Val = AnyValue(RandomVal);
891 else if (Ty->isFloatingPointTy())
892 Val = AnyValue(APFloat(Ty->getFltSemantics(), RandomVal));
893 else if (Ty->isPointerTy())
894 Val = AnyValue(Pointer(RandomVal));
895 else
896 llvm_unreachable("Unsupported scalar type for poison value");
897 return;
898 }
899 if (Val.isByte()) {
900 for (Byte &V : Val.asMutableByte().mutableBytes()) {
901 if (V.ConcreteMask == 255)
902 continue;
903 uint8_t OldMask = V.ConcreteMask;
904 V.ConcreteMask = 255;
905 V.Value &= OldMask;
906 if (mayUseNonDeterminism())
907 V.Value |= (Rng() & 255) & ~OldMask;
908 }
909 return;
910 }
911 if (Val.isAggregate()) {
912 auto &SubVals = Val.asAggregate();
913 if (auto *VecTy = dyn_cast<VectorType>(Val: Ty)) {
914 Type *ElemTy = VecTy->getElementType();
915 for (auto &SubVal : SubVals)
916 freeze(Val&: SubVal, Ty: ElemTy);
917 } else if (auto *ArrTy = dyn_cast<ArrayType>(Val: Ty)) {
918 Type *ElemTy = ArrTy->getElementType();
919 for (auto &SubVal : SubVals)
920 freeze(Val&: SubVal, Ty: ElemTy);
921 } else if (auto *StructTy = dyn_cast<StructType>(Val: Ty)) {
922 for (uint32_t I = 0, E = SubVals.size(); I != E; ++I)
923 freeze(Val&: SubVals[I], Ty: StructTy->getElementType(N: I));
924 } else {
925 llvm_unreachable("Invalid aggregate type");
926 }
927 }
928}
929
930AnyValue Context::computePtrAdd(const Pointer &Ptr, const APInt &Offset,
931 GEPNoWrapFlags Flags,
932 AnyValue &AccumulatedOffset) {
933 if (Offset.isZero())
934 return Ptr;
935 APInt IndexBits = Ptr.address().trunc(width: Offset.getBitWidth());
936 auto NewIndex =
937 addNoWrap(LHS: IndexBits, RHS: Offset, /*HasNSW=*/false, HasNUW: Flags.hasNoUnsignedWrap());
938 if (NewIndex.isPoison())
939 return AnyValue::poison();
940 if (Flags.hasNoUnsignedSignedWrap()) {
941 // The successive addition of the current address, truncated to the
942 // pointer index type and interpreted as an unsigned number, and each
943 // offset, interpreted as a signed number, does not wrap the pointer index
944 // type.
945 if (Offset.isNonNegative() ? NewIndex.asInteger().ult(RHS: IndexBits)
946 : NewIndex.asInteger().ugt(RHS: IndexBits))
947 return AnyValue::poison();
948 }
949 APInt NewAddr = Ptr.address();
950 NewAddr.insertBits(SubBits: NewIndex.asInteger(), bitPosition: 0);
951
952 MemoryObject *MO = nullptr;
953 if (Flags.isInBounds()) {
954 MO = checkProvenance(
955 Ptr, Check: [](const Provenance &) { return true; },
956 /*HasSideEffect=*/false);
957 if (!MO || !MO->inBounds(NewAddr))
958 return AnyValue::poison();
959 }
960
961 if (!AccumulatedOffset.isPoison()) {
962 AccumulatedOffset =
963 addNoWrap(LHS: AccumulatedOffset.asInteger(), RHS: Offset,
964 HasNSW: Flags.hasNoUnsignedSignedWrap(), HasNUW: Flags.hasNoUnsignedWrap());
965 if (AccumulatedOffset.isPoison())
966 return AnyValue::poison();
967 }
968
969 // Should not expose provenance here even if the new address doesn't point
970 // to the original object.
971 auto Res = Ptr.getWithNewAddr(NewAddr);
972 if (MO) {
973 auto &Prov = Res.provenance();
974 if (Prov.isWildcard() && !Prov.getMemoryObject())
975 Res = Res.getWithNewProvenance(NewProv: Prov.getWithKnownMemoryObject(Obj&: *MO));
976 }
977 return Res;
978}
979
980AnyValue Context::computePtrAdd(const AnyValue &Ptr, const APInt &Offset,
981 GEPNoWrapFlags Flags,
982 AnyValue &AccumulatedOffset) {
983 if (Ptr.isPoison())
984 return AnyValue::poison();
985 return computePtrAdd(Ptr: Ptr.asPointer(), Offset, Flags, AccumulatedOffset);
986}
987
988AnyValue Context::computeScaledPtrAdd(const AnyValue &Ptr,
989 const AnyValue &Index, const APInt &Scale,
990 GEPNoWrapFlags Flags,
991 AnyValue &AccumulatedOffset) {
992 if (Ptr.isPoison() || Index.isPoison())
993 return AnyValue::poison();
994 assert(Ptr.isPointer() && Index.isInteger() && "Unexpected type.");
995 if (Scale.isOne())
996 return computePtrAdd(Ptr, Offset: Index.asInteger(), Flags, AccumulatedOffset);
997 auto ScaledOffset =
998 mulNoWrap(LHS: Index.asInteger(), RHS: Scale, HasNSW: Flags.hasNoUnsignedSignedWrap(),
999 HasNUW: Flags.hasNoUnsignedWrap());
1000 if (ScaledOffset.isPoison())
1001 return AnyValue::poison();
1002 return computePtrAdd(Ptr, Offset: ScaledOffset.asInteger(), Flags, AccumulatedOffset);
1003}
1004
1005static AnyValue canonicalizeIndex(const AnyValue &Idx, unsigned IndexBitWidth,
1006 GEPNoWrapFlags Flags) {
1007 if (Idx.isPoison())
1008 return AnyValue::poison();
1009 auto &IdxInt = Idx.asInteger();
1010 if (IdxInt.getBitWidth() == IndexBitWidth)
1011 return Idx;
1012 if (IdxInt.getBitWidth() > IndexBitWidth) {
1013 if (Flags.hasNoUnsignedSignedWrap() && !IdxInt.isSignedIntN(N: IndexBitWidth))
1014 return AnyValue::poison();
1015
1016 if (Flags.hasNoUnsignedWrap() && !IdxInt.isIntN(N: IndexBitWidth))
1017 return AnyValue::poison();
1018
1019 return IdxInt.trunc(width: IndexBitWidth);
1020 }
1021 return IdxInt.sext(width: IndexBitWidth);
1022}
1023
1024AnyValue
1025Context::computeGEP(GEPOperator &GEP,
1026 function_ref<const AnyValue &(Value *V)> GetValue) {
1027 uint32_t IndexBitWidth =
1028 DL.getIndexSizeInBits(AS: GEP.getType()->getPointerAddressSpace());
1029 GEPNoWrapFlags Flags = GEP.getNoWrapFlags();
1030 AnyValue Res = GetValue(GEP.getPointerOperand());
1031 AnyValue AccumulatedOffset = APInt(IndexBitWidth, 0);
1032 if (Res.isAggregate())
1033 AccumulatedOffset =
1034 AnyValue::getVectorSplat(Scalar: AccumulatedOffset, NumElements: Res.asAggregate().size());
1035 auto ApplyScaledOffset = [&](const AnyValue &Index, const APInt &Scale) {
1036 if (Index.isAggregate()) {
1037 assert(Res.isAggregate() && "Res must be splatted before.");
1038 for (auto &&[ResElem, IndexElem, OffsetElem] :
1039 zip(t&: Res.asAggregate(), u: Index.asAggregate(),
1040 args&: AccumulatedOffset.asAggregate()))
1041 ResElem = computeScaledPtrAdd(
1042 Ptr: ResElem, Index: canonicalizeIndex(Idx: IndexElem, IndexBitWidth, Flags), Scale,
1043 Flags, AccumulatedOffset&: OffsetElem);
1044 } else {
1045 AnyValue CanonicalIndex = canonicalizeIndex(Idx: Index, IndexBitWidth, Flags);
1046 if (Res.isAggregate()) {
1047 for (auto &&[ResElem, OffsetElem] :
1048 zip(t&: Res.asAggregate(), u&: AccumulatedOffset.asAggregate()))
1049 ResElem = computeScaledPtrAdd(Ptr: ResElem, Index: CanonicalIndex, Scale, Flags,
1050 AccumulatedOffset&: OffsetElem);
1051 } else {
1052 Res = computeScaledPtrAdd(Ptr: Res, Index: CanonicalIndex, Scale, Flags,
1053 AccumulatedOffset);
1054 }
1055 }
1056 };
1057
1058 for (gep_type_iterator GTI = gep_type_begin(GEP), GTE = gep_type_end(GEP);
1059 GTI != GTE; ++GTI) {
1060 Value *V = GTI.getOperand();
1061
1062 // If the index is a vector, make sure the accumulated pointer is also a
1063 // vector. Otherwise, make it a vector splat.
1064 if (auto *VTy = dyn_cast<VectorType>(Val: V->getType());
1065 VTy && !Res.isAggregate()) {
1066 uint32_t NumElements = getEVL(EC: VTy->getElementCount());
1067 Res = AnyValue::getVectorSplat(Scalar: Res, NumElements);
1068 AccumulatedOffset =
1069 AnyValue::getVectorSplat(Scalar: AccumulatedOffset, NumElements);
1070 }
1071
1072 // Fast path for zero offsets.
1073 if (auto *CI = dyn_cast<ConstantInt>(Val: V)) {
1074 if (CI->isZero())
1075 continue;
1076 }
1077 if (isa<ConstantAggregateZero>(Val: V))
1078 continue;
1079
1080 // Handle a struct index, which adds its field offset to the pointer.
1081 if (StructType *STy = GTI.getStructTypeOrNull()) {
1082 unsigned ElementIdx =
1083 cast<Constant>(Val: V)->getUniqueInteger().getZExtValue();
1084 const StructLayout *SL = DL.getStructLayout(Ty: STy);
1085 // Element offset is in bytes.
1086 ApplyScaledOffset(APInt(IndexBitWidth, SL->getElementOffset(Idx: ElementIdx),
1087 /*isSigned=*/false, /*implicitTrunc=*/true),
1088 APInt(IndexBitWidth, 1));
1089 continue;
1090 }
1091
1092 // Truncate if type size exceeds index space.
1093 // TODO: Should be documented in LangRef: GEPs with nowrap flags should
1094 // return poison when the type size exceeds index space.
1095 TypeSize Offset = GTI.getSequentialElementStride(DL);
1096 APInt Scale(IndexBitWidth, getEffectiveTypeSize(Size: Offset),
1097 /*isSigned=*/false, /*implicitTrunc=*/true);
1098 if (!Scale.isZero())
1099 ApplyScaledOffset(GetValue(V), Scale);
1100 }
1101 return Res;
1102}
1103
1104MemoryObject::~MemoryObject() = default;
1105MemoryObject::MemoryObject(uint64_t Addr, uint64_t Size, StringRef Name,
1106 unsigned AS, MemInitKind InitKind,
1107 MemAllocKind AllocKind, bool IsIRGlobalValue)
1108 : Address(Addr), Size(Size), Name(Name), AS(AS),
1109 State(InitKind != MemInitKind::Poisoned ? MemoryObjectState::Alive
1110 : MemoryObjectState::Dead),
1111 AllocKind(AllocKind), IsIRGlobalValue(IsIRGlobalValue) {
1112 switch (InitKind) {
1113 case MemInitKind::Zeroed:
1114 Bytes.resize(N: Size, NV: Byte::concrete(Val: 0));
1115 break;
1116 case MemInitKind::Uninitialized:
1117 Bytes.resize(N: Size, NV: Byte::undef());
1118 break;
1119 case MemInitKind::Poisoned:
1120 Bytes.resize(N: Size, NV: Byte::poison());
1121 break;
1122 }
1123}
1124
1125IntrusiveRefCntPtr<MemoryObject>
1126Context::allocate(uint64_t Size, uint64_t Align, StringRef Name, unsigned AS,
1127 MemInitKind InitKind, MemAllocKind AllocKind,
1128 bool IsIRGlobalValue) {
1129 // Even if the memory object is zero-sized, it still occupies a byte to obtain
1130 // a unique address.
1131 uint64_t AllocateSize = std::max(a: Size, b: (uint64_t)1);
1132 if (SaturatingAdd(X: UsedMem, Y: AllocateSize) >= MaxMem)
1133 return nullptr;
1134 uint64_t AlignedAddr = alignTo(Value: AllocationBase, Align);
1135 unsigned AddressBW = DL.getAddressSizeInBits(AS);
1136 // Make sure the address can be represented.
1137 if (!isUIntN(N: AddressBW, x: AlignedAddr))
1138 return nullptr;
1139 auto MemObj = makeIntrusiveRefCnt<MemoryObject>(
1140 A&: AlignedAddr, A&: Size, A&: Name, A&: AS, A&: InitKind, A&: AllocKind, A&: IsIRGlobalValue);
1141 MemoryObjects[AlignedAddr] = MemObj;
1142 // Extra padding to make sure getWildcardProvenance resolves to at most one
1143 // memory object.
1144 AllocationBase = AlignedAddr + AllocateSize + 1;
1145 UsedMem += AllocateSize;
1146 return MemObj;
1147}
1148
1149bool Context::free(const MemoryObject &Obj) {
1150 uint64_t Address = Obj.getAddress();
1151 auto It = MemoryObjects.find(Val: Address);
1152 if (It == MemoryObjects.end() || It->second.get() != &Obj)
1153 return false;
1154
1155 UsedMem -= std::max(a: It->second->getSize(), b: static_cast<uint64_t>(1));
1156
1157 MemoryObject &MutableObj = *It->second;
1158 MutableObj.State = MemoryObjectState::Freed;
1159 MutableObj.Bytes.clear();
1160 for (const APInt &Tag : MutableObj.AssociatedTags)
1161 TaggedProvenances.erase(Val: Tag);
1162 MutableObj.AssociatedTags.clear();
1163 ExposedProvenances.erase(x: Address);
1164
1165 MemoryObjects.erase(I: It);
1166 return true;
1167}
1168
1169Pointer Context::deriveFromMemoryObject(IntrusiveRefCntPtr<MemoryObject> Obj) {
1170 assert(Obj && "Cannot determine the address space of a null memory object");
1171 return Pointer(makeIntrusiveRefCnt<Provenance>(A&: Obj),
1172 APInt(DL.getPointerSizeInBits(AS: Obj->getAddressSpace()),
1173 Obj->getAddress()));
1174}
1175
1176void Context::exposeProvenance(Provenance &Prov) {
1177 if (Prov.Wildcard)
1178 return;
1179 MemoryObject *Obj = Prov.getMemoryObject();
1180 if (!Obj)
1181 return;
1182 uint64_t Address = Obj->getAddress();
1183 ExposedProvenanceSet &Set = ExposedProvenances[Address];
1184 if (Set.Set.insert(Ptr: &Prov).second)
1185 Set.List.push_back(Elt: {.Prov: &Prov, .Generation: ++ExposedProvenanceSetGeneration});
1186}
1187
1188MemoryObject *
1189Context::checkProvenance(const Pointer &Ptr,
1190 function_ref<bool(const Provenance &)> Check,
1191 bool HasSideEffect) {
1192 auto &Prov = Ptr.provenance();
1193 if (!Check(Prov))
1194 return nullptr;
1195 // Early return for concrete provenances.
1196 if (!Prov.Wildcard)
1197 return Prov.Obj.get();
1198
1199 MemoryObject *MO = nullptr;
1200 APInt &Mask = Prov.Wildcard->ActiveMask;
1201 SmallVector<ExposedProvenance> *List = nullptr;
1202 uint32_t ProvenanceCount = 0;
1203 if (Mask.isZero()) {
1204 // The memory object hasn't been determined.
1205 uint64_t Addr = Ptr.address().getLimitedValue();
1206 auto Iter = ExposedProvenances.upper_bound(x: Addr);
1207 if (Iter == ExposedProvenances.begin())
1208 return nullptr;
1209 auto &[BaseAddress, Set] = *std::prev(x: Iter);
1210 auto &Obj = MemoryObjects.at(Val: BaseAddress);
1211 if (!Obj->inBounds(NewAddr: Ptr.address()))
1212 return nullptr;
1213 MO = Obj.get();
1214 // We only inspect the first N exposed provenances according to the global
1215 // generation number of the wildcard pointer.
1216 ProvenanceCount = std::distance(
1217 first: Set.List.begin(),
1218 last: upper_bound(Range&: Set.List,
1219 Value: ExposedProvenance{.Prov: nullptr, .Generation: Prov.Wildcard->Generation}));
1220 if (HasSideEffect) {
1221 Mask = APInt::getAllOnes(numBits: ProvenanceCount);
1222 Prov.Wildcard->BaseAddress = BaseAddress;
1223 }
1224 List = &Set.List;
1225 } else {
1226 // We already determined the memory object in a previous memory access.
1227 uint64_t BaseAddress = Prov.Wildcard->BaseAddress;
1228 auto Iter = ExposedProvenances.find(x: BaseAddress);
1229 // The memory object has been freed.
1230 if (Iter == ExposedProvenances.end())
1231 return nullptr;
1232 MO = MemoryObjects.at(Val: BaseAddress).get();
1233 if (!MO->inBounds(NewAddr: Ptr.address()))
1234 return nullptr;
1235 List = &Iter->second.List;
1236 ProvenanceCount = Mask.getBitWidth();
1237 }
1238 if (Prov.Obj) {
1239 // We already determined the memory object via speculatable operations like
1240 // gep inbounds.
1241 if (Prov.Obj.get() != MO)
1242 return nullptr;
1243 }
1244
1245 bool Valid = false;
1246 for (uint32_t I = 0; I != ProvenanceCount; ++I) {
1247 assert((!HasSideEffect || !Mask.isZero()) &&
1248 "Mask must be initialized if HasSideEffect is true.");
1249 if (!Mask.isZero() && !Mask[I])
1250 continue;
1251 if (Check(*(*List)[I].Prov)) {
1252 Valid = true;
1253 // Early return as we don't need to update the Mask.
1254 if (!HasSideEffect)
1255 break;
1256 } else if (HasSideEffect)
1257 Mask.clearBit(BitPosition: I);
1258 }
1259
1260 return Valid ? MO : nullptr;
1261}
1262
1263IntrusiveRefCntPtr<Provenance> Context::getWildcardProvenance() {
1264 // No exposed provenances.
1265 if (ExposedProvenanceSetGeneration == 0)
1266 return Provenance::nullary();
1267 auto Prov = makeIntrusiveRefCnt<Provenance>(A: nullptr);
1268 Prov->Wildcard =
1269 makeIntrusiveRefCnt<WildcardProvenance>(A&: ExposedProvenanceSetGeneration);
1270 return Prov;
1271}
1272
1273Function *Context::getTargetFunction(const Pointer &Ptr) {
1274 if (Ptr.address().getActiveBits() > 64)
1275 return nullptr;
1276 auto It = ValidFuncTargets.find(Val: Ptr.address().getZExtValue());
1277 if (It == ValidFuncTargets.end())
1278 return nullptr;
1279 // TODO: check the provenance of pointer.
1280 return It->second.first;
1281}
1282BasicBlock *Context::getTargetBlock(const Pointer &Ptr) {
1283 if (Ptr.address().getActiveBits() > 64)
1284 return nullptr;
1285 auto It = ValidBlockTargets.find(Val: Ptr.address().getZExtValue());
1286 if (It == ValidBlockTargets.end())
1287 return nullptr;
1288 // TODO: check the provenance of pointer.
1289 return It->second.first;
1290}
1291
1292uint64_t Context::getEffectiveTypeAllocSize(Type *Ty) {
1293 // FIXME: It is incorrect for overaligned scalable vector types.
1294 return getEffectiveTypeSize(Size: DL.getTypeAllocSize(Ty));
1295}
1296uint64_t Context::getEffectiveTypeStoreSize(Type *Ty) {
1297 return getEffectiveTypeSize(Size: DL.getTypeStoreSize(Ty));
1298}
1299
1300RoundingMode Context::getCurrentRoundingMode() const {
1301 return CurrentRoundingMode;
1302}
1303
1304fp::ExceptionBehavior Context::getCurrentExceptionBehavior() const {
1305 return CurrentExceptionBehavior;
1306}
1307
1308void Context::setCurrentRoundingMode(RoundingMode RM) {
1309 CurrentRoundingMode = RM;
1310}
1311
1312void Context::setCurrentExceptionBehavior(fp::ExceptionBehavior EB) {
1313 CurrentExceptionBehavior = EB;
1314}
1315
1316bool Context::isDefaultFPEnv() const {
1317 return isDefaultFPEnvironment(EB: CurrentExceptionBehavior, RM: CurrentRoundingMode);
1318}
1319
1320UndefValueBehavior Context::getEffectiveUndefValueBehavior() const {
1321 if (isDeterministic())
1322 return UndefValueBehavior::Zero;
1323 return UndefBehavior;
1324}
1325
1326NaNPropagationBehavior Context::getEffectiveNaNPropagationBehavior() const {
1327 if (isDeterministic())
1328 return NaNPropagationBehavior::PreferredNaN;
1329 return NaNBehavior;
1330}
1331
1332bool Context::getRandomBool() {
1333 // We use the lowest bit of the raw bits from RNG as the result:
1334 if (mayUseNonDeterminism())
1335 return static_cast<bool>(Rng() & 1);
1336 return false;
1337}
1338
1339uint64_t Context::getRandomUInt64() {
1340 if (mayUseNonDeterminism())
1341 return Rng();
1342 return 0;
1343}
1344
1345bool MemoryObject::isGlobal() const {
1346 return AllocKind == MemAllocKind::Global;
1347}
1348
1349bool MemoryObject::isStackAllocated() const {
1350 return AllocKind == MemAllocKind::Stack;
1351}
1352
1353bool MemoryObject::isHeapAllocated() const {
1354 switch (AllocKind) {
1355 case MemAllocKind::Global:
1356 case MemAllocKind::BlockAddress:
1357 case MemAllocKind::Stack:
1358 return false;
1359 case MemAllocKind::Malloc:
1360 case MemAllocKind::New:
1361 case MemAllocKind::NewArray:
1362 return true;
1363 }
1364
1365 llvm_unreachable("Unknown MemAllocKind");
1366}
1367
1368} // namespace llvm::ubi
1369