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