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