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