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