1//===--- Value.h - Value Representation for llubi ---------------*- C++ -*-===//
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#ifndef LLVM_TOOLS_LLUBI_VALUE_H
10#define LLVM_TOOLS_LLUBI_VALUE_H
11
12#include "llvm/ADT/APFloat.h"
13#include "llvm/ADT/APInt.h"
14#include "llvm/ADT/IntrusiveRefCntPtr.h"
15#include "llvm/IR/DataLayout.h"
16#include "llvm/IR/Type.h"
17#include "llvm/Support/raw_ostream.h"
18
19namespace llvm::ubi {
20
21class MemoryObject;
22class Context;
23class AnyValue;
24
25/// Representation of a byte in memory.
26/// How to interpret the byte per bit:
27/// - If the concrete mask bit is 0, the bit is either undef or poison. The
28/// value bit indicates whether it is undef.
29/// - If the concrete mask bit is 1, the bit is a concrete value. The value bit
30/// stores the concrete bit value. The tag mask bit indicates whether it is a
31/// pointer bit, and the tag value bit is used for provenance tracking of
32/// pointers.
33///
34/// Note that the idealized interpreter would store a full pointer tag for every
35/// single pointer bit, as well as the position of that bit in the pointer. The
36/// provenance is preserved as the bit is copied around, and when a sequence of
37/// bytes is eventually converted back to a pointer, all bits must be in the
38/// original order and have the same provenance. However, that would be
39/// prohibitively expensive. So instead, we rely on randomized ptr-sized tags.
40/// This means that if bits get reordered, or if bits from different pointers
41/// get mixed, then the result is unlikely to be a valid tag.
42struct Byte {
43 uint8_t ConcreteMask;
44 uint8_t Value;
45 uint8_t TagMask; // A mask to indicate which bits are pointer bits.
46 uint8_t TagValue; // For each pointer bit, the corresponding bit of the tag
47 // for provenance tracking.
48
49 static Byte poison() { return Byte{.ConcreteMask: 0, .Value: 0, .TagMask: 0, .TagValue: 0}; }
50 static Byte undef() { return Byte{.ConcreteMask: 0, .Value: 255, .TagMask: 0, .TagValue: 0}; }
51 static Byte concrete(uint8_t Val) { return Byte{.ConcreteMask: 255, .Value: Val, .TagMask: 0, .TagValue: 0}; }
52
53 void zeroBits(uint8_t Mask) {
54 ConcreteMask |= Mask;
55 Value &= ~Mask;
56 TagMask &= ~Mask;
57 }
58
59 void poisonBits(uint8_t Mask) {
60 ConcreteMask &= ~Mask;
61 Value &= ~Mask;
62 TagMask &= ~Mask;
63 }
64
65 void undefBits(uint8_t Mask) {
66 ConcreteMask &= ~Mask;
67 Value |= Mask;
68 TagMask &= ~Mask;
69 }
70
71 void writeBits(uint8_t Mask, uint8_t Val) {
72 ConcreteMask |= Mask;
73 Value = (Value & ~Mask) | (Val & Mask);
74 TagMask &= ~Mask;
75 }
76
77 void writeTagBits(uint8_t Mask, uint8_t Tag) {
78 assert(
79 (ConcreteMask & Mask) == Mask &&
80 "Please ensure pointer bits are concrete before calling writeTagBits.");
81 TagMask |= Mask;
82 TagValue = (TagValue & ~Mask) | (Tag & Mask);
83 }
84
85 void writeByte(uint8_t Mask, const Byte &RHS) {
86 ConcreteMask = (ConcreteMask & ~Mask) | (RHS.ConcreteMask & Mask);
87 Value = (Value & ~Mask) | (RHS.Value & Mask);
88 TagMask = (TagMask & ~Mask) | (RHS.TagMask & Mask);
89 TagValue = (TagValue & ~Mask) | (RHS.TagValue & Mask);
90 }
91
92 /// Returns a logical byte that is part of two adjacent bytes.
93 /// Example with ShAmt = 5:
94 /// | Low | High |
95 /// LSB | 0 1 0 1 0 1 0 1 | 0 0 0 0 1 1 1 1 | MSB
96 /// Result = | 1 0 1 0 0 0 0 1 |
97 static Byte fshr(const Byte &Low, const Byte &High, uint32_t ShAmt) {
98 return Byte{
99 .ConcreteMask: static_cast<uint8_t>((Low.ConcreteMask | (High.ConcreteMask << 8)) >>
100 ShAmt),
101 .Value: static_cast<uint8_t>((Low.Value | (High.Value << 8)) >> ShAmt),
102 .TagMask: static_cast<uint8_t>((Low.TagMask | (High.TagMask << 8)) >> ShAmt),
103 .TagValue: static_cast<uint8_t>((Low.TagValue | (High.TagValue << 8)) >> ShAmt)};
104 }
105
106 Byte lshr(uint8_t Shift) const {
107 return Byte{.ConcreteMask: static_cast<uint8_t>(ConcreteMask >> Shift),
108 .Value: static_cast<uint8_t>(Value >> Shift),
109 .TagMask: static_cast<uint8_t>(TagMask >> Shift),
110 .TagValue: static_cast<uint8_t>(TagValue >> Shift)};
111 }
112
113 Byte shl(uint8_t Shift) const {
114 return Byte{.ConcreteMask: static_cast<uint8_t>(ConcreteMask << Shift),
115 .Value: static_cast<uint8_t>(Value << Shift),
116 .TagMask: static_cast<uint8_t>(TagMask << Shift),
117 .TagValue: static_cast<uint8_t>(TagValue << Shift)};
118 }
119
120 /// Padding bits may carry pointer provenance. Only require their value bits
121 /// to be concrete zero, or non-concrete for poison.
122 bool isCanonicalPaddingByte(uint8_t PaddingMask) const {
123 bool AreAllValueBitsPoison = (ConcreteMask & ~PaddingMask) == 0;
124 return (ConcreteMask & PaddingMask) ==
125 (AreAllValueBitsPoison ? 0 : PaddingMask) &&
126 (Value & PaddingMask) == 0;
127 }
128};
129
130enum class StorageKind {
131 Integer,
132 Float,
133 Pointer,
134 Byte,
135 Poison,
136 None, // Placeholder for void type
137 Aggregate, // Struct, Array or Vector
138};
139
140/// Tri-state boolean value.
141enum class BooleanKind { False, True, Poison };
142
143/// A set of previously exposed provenances. It is originally yielded by
144/// inttoptr, and shared by pointers derived from the result.
145///
146/// Each capability check may invalidate some provenances. If we cannot
147/// pick one, it is UB. That is, from the angelic non-determinism view,
148/// we cannot pick a provenance to make the program reach this point.
149///
150/// For efficiency, this class has different forms in two stages:
151/// 1. Before any memory access is performed, ActiveMask is set to zero and
152/// Generation represents the global generation number of the snapshot.
153/// 2. After a memory access is performed, we can determine exactly one memory
154/// object to be accessed (address ranges are distinct). In this case,
155/// BaseAddress is set and ActiveMask is non-zero. ActiveMask represents the
156/// validity of the first N exposed provenances associated with the memory
157/// object. The bitwidth N is the number of provenances in the list with
158/// List[I].Generation <= WildcardProvenance::Generation (The generation field
159/// in the list is monotonically increasing). That is, we can only access
160/// through exposed provenances before inttoptr executes. Note that if
161/// ActiveMask becomes zero again, UB must be triggered.
162class WildcardProvenance : public RefCountedBase<WildcardProvenance> {
163 APInt ActiveMask;
164 union {
165 uint64_t Generation;
166 uint64_t BaseAddress;
167 };
168
169 friend class Context;
170
171public:
172 explicit WildcardProvenance(uint64_t Generation)
173 : ActiveMask(), Generation(Generation) {}
174};
175
176/// Components of a pointer excluding address. They are shared between pointer
177/// values, as most of operations don't change the provenance.
178/// Each node will be assigned a unique, pointer-sized tag, which is used to
179/// represent the pointer in the memory.
180/// The provenance can be either concrete or wildcard, as determined by the
181/// cases below:
182/// Obj Wildcard State
183/// Null Null Invalid
184/// Null NonNull Wildcard
185/// NonNull Null Concrete
186/// NonNull NonNull Wildcard (associated with a specific MO)
187class Provenance : public RefCountedBase<Provenance> {
188 // TODO: store reference to the provenance of the pointer it is derived from
189
190 // The underlying memory object. It can be null for invalid or dangling
191 // pointers. Besides, for pointers with wildcard provenance, it can be null
192 // until the memory object is resolved by gep inbounds.
193 IntrusiveRefCntPtr<MemoryObject> Obj;
194
195 // A tag is a randomly generated unique identifier to recover the provenance
196 // of a pointer. The length of tag is equal to the store size of the pointer
197 // type, in bits. It may produce false negatives in some corner cases. But in
198 // real practice the false negative rate should be negligible.
199 // A zero tag is invalid.
200 APInt Tag;
201
202 // Null if it is concrete.
203 IntrusiveRefCntPtr<WildcardProvenance> Wildcard;
204
205 // TODO: modeling nofree
206 // TODO: modeling captures
207 // TODO: modeling inrange(Start, End) attribute
208
209 const APInt &getTag() const { return Tag; }
210 void setTag(const APInt &T) { Tag = T; }
211
212 friend class Context;
213
214public:
215 Provenance(IntrusiveRefCntPtr<MemoryObject> Obj) : Obj(std::move(Obj)) {}
216 static IntrusiveRefCntPtr<Provenance> nullary();
217 IntrusiveRefCntPtr<Provenance> getWithKnownMemoryObject(MemoryObject &Obj);
218 MemoryObject *getMemoryObject() const { return Obj.get(); }
219 bool isWildcard() const { return Wildcard != nullptr; }
220};
221
222class Pointer {
223 // The provenance of the pointer.
224 IntrusiveRefCntPtr<Provenance> Prov;
225 // The address of the pointer. The bit width is determined by
226 // DataLayout::getPointerSizeInBits.
227 APInt Address;
228
229public:
230 explicit Pointer(const APInt &Address)
231 : Prov(Provenance::nullary()), Address(Address) {}
232 explicit Pointer(IntrusiveRefCntPtr<Provenance> Prov, const APInt &Address)
233 : Prov(std::move(Prov)), Address(Address) {
234 assert(this->Prov && "Invalid provenance.");
235 }
236 Pointer getWithNewAddr(const APInt &NewAddr) const {
237 return Pointer(Prov, NewAddr);
238 }
239 Pointer getWithNewProvenance(IntrusiveRefCntPtr<Provenance> NewProv) const {
240 return Pointer(NewProv, Address);
241 }
242 static AnyValue null(unsigned AS, const DataLayout &DL);
243 bool isNullPtr(unsigned AS, const DataLayout &DL) const;
244 void print(raw_ostream &OS) const;
245 const APInt &address() const { return Address; }
246 Provenance &provenance() const { return *Prov; }
247};
248
249/// Represents a scalar byte value. If the value is not byte-sized, the padding
250/// bits are guaranteed to be filled by either poison/zero bits.
251///
252/// Byte values do not contain undef bits. The only exception is
253/// Context::fromBytes, which converts undef bits into poison bits after
254/// constructor.
255class ByteValue {
256 // The byte order is endianness-dependent.
257 std::vector<Byte> Val;
258 uint32_t BitWidth : 31;
259 uint32_t IsLittleEndian : 1;
260
261public:
262 /// Specify how to treat the input.
263 enum class CanonicalizeMode {
264 // The padding byte is already canonical.
265 Canonical,
266 // Determine the padding bits from the non-padding bits in the padding
267 // byte.
268 PaddingFromValue,
269 // Set the padding byte to poison when it is non-canonical.
270 FlushNonCanonicalToPoison,
271 };
272
273 ByteValue(const APInt &V, bool IsLittleEndian);
274 ByteValue(uint32_t BitWidth, ArrayRef<Byte> Val, bool IsLittleEndian,
275 CanonicalizeMode Mode = CanonicalizeMode::Canonical)
276 : ByteValue(BitWidth, std::vector<Byte>(Val), IsLittleEndian, Mode) {}
277 ByteValue(uint32_t BitWidth, std::vector<Byte> Val, bool IsLittleEndian,
278 CanonicalizeMode Mode = CanonicalizeMode::Canonical)
279 : Val(std::move(Val)), BitWidth(BitWidth),
280 IsLittleEndian(IsLittleEndian) {
281 if (Mode == CanonicalizeMode::Canonical)
282 assert(isValid() && "Input padding bits must be canonical.");
283 else
284 canonicalize(Mode);
285 }
286 ByteValue(const ByteValue &) = default;
287 ByteValue(ByteValue &&) = default;
288 ByteValue &operator=(const ByteValue &) = default;
289 ByteValue &operator=(ByteValue &&) = default;
290 ~ByteValue() = default;
291
292 static ByteValue zero(uint32_t BitWidth, bool IsLittleEndian);
293 static ByteValue poison(uint32_t BitWidth, bool IsLittleEndian);
294
295 uint32_t getBitWidth() const { return BitWidth; }
296 ArrayRef<Byte> bytes() const { return Val; }
297 /// The caller should call canonicalize after mutation.
298 MutableArrayRef<Byte> mutableBytes() { return Val; }
299
300 /// Make sure the padding byte is canonical.
301 void canonicalize(CanonicalizeMode Mode) {
302 assert(Mode != CanonicalizeMode::Canonical &&
303 "Canonical padding bits should not be canonicalized.");
304 if ((BitWidth & 7) == 0)
305 return;
306 uint8_t Mask = static_cast<uint8_t>((~0U) << (BitWidth & 7));
307 Byte &MSB = (IsLittleEndian ? this->Val.back() : this->Val.front());
308 if (Mode == CanonicalizeMode::FlushNonCanonicalToPoison) {
309 if (!MSB.isCanonicalPaddingByte(PaddingMask: Mask))
310 MSB = Byte::poison();
311 } else {
312 if ((MSB.ConcreteMask & ~Mask) == 0)
313 MSB.poisonBits(Mask);
314 else
315 MSB.zeroBits(Mask);
316 }
317 assert(isValid() && "Padding bits must be canonical.");
318 }
319
320 bool isValid() const {
321 if ((BitWidth & 7) == 0)
322 return true;
323 uint8_t Mask = static_cast<uint8_t>((~0U) << (BitWidth & 7));
324 const Byte &MSB = (IsLittleEndian ? this->Val.back() : this->Val.front());
325 return MSB.isCanonicalPaddingByte(PaddingMask: Mask);
326 }
327
328 void print(Context &Ctx, raw_ostream &OS) const;
329};
330
331// Value representation for actual values of LLVM values.
332// We don't model undef values here (except for byte types).
333class [[nodiscard]] AnyValue {
334 StorageKind Kind;
335 union {
336 APInt IntVal;
337 APFloat FloatVal;
338 Pointer PtrVal;
339 ByteValue ByteVal;
340 std::vector<AnyValue> AggVal;
341 };
342
343 struct PoisonTag {};
344 void destroy();
345
346public:
347 AnyValue() : Kind(StorageKind::None) {}
348 explicit AnyValue(PoisonTag) : Kind(StorageKind::Poison) {}
349 AnyValue(APInt Val) : Kind(StorageKind::Integer), IntVal(std::move(Val)) {}
350 AnyValue(APFloat Val) : Kind(StorageKind::Float), FloatVal(std::move(Val)) {}
351 AnyValue(Pointer Val) : Kind(StorageKind::Pointer), PtrVal(std::move(Val)) {}
352 AnyValue(ByteValue Val) : Kind(StorageKind::Byte), ByteVal(std::move(Val)) {}
353 AnyValue(std::vector<AnyValue> Val)
354 : Kind(StorageKind::Aggregate), AggVal(std::move(Val)) {}
355 AnyValue(const AnyValue &Other);
356 AnyValue(AnyValue &&Other);
357 AnyValue &operator=(const AnyValue &);
358 AnyValue &operator=(AnyValue &&);
359 ~AnyValue() { destroy(); }
360
361 void print(Context &Ctx, raw_ostream &OS) const;
362
363 /// Use getPoisonValue unless you know the scalar type is integer/fp/ptr!
364 static AnyValue poison() { return AnyValue(PoisonTag{}); }
365 static AnyValue boolean(bool Val) { return AnyValue(APInt(1, Val)); }
366 static AnyValue getPoisonValue(Context &Ctx, Type *Ty);
367 static AnyValue getNullValue(Context &Ctx, Type *Ty);
368 static AnyValue getVectorSplat(const AnyValue &Scalar, size_t NumElements);
369
370 bool isNone() const { return Kind == StorageKind::None; }
371 bool isPoison() const { return Kind == StorageKind::Poison; }
372 bool isInteger() const { return Kind == StorageKind::Integer; }
373 bool isFloat() const { return Kind == StorageKind::Float; }
374 bool isPointer() const { return Kind == StorageKind::Pointer; }
375 bool isByte() const { return Kind == StorageKind::Byte; }
376 bool isAggregate() const { return Kind == StorageKind::Aggregate; }
377
378 bool isCompatibleWith(Type *Ty) const {
379 switch (Kind) {
380 case StorageKind::None:
381 return Ty->isVoidTy();
382 case StorageKind::Poison:
383 return Ty->isFloatingPointTy() || Ty->isIntegerTy() || Ty->isPointerTy();
384 case StorageKind::Integer:
385 return Ty->isIntegerTy();
386 case StorageKind::Float:
387 return Ty->isFloatingPointTy();
388 case StorageKind::Pointer:
389 return Ty->isPointerTy();
390 case StorageKind::Byte:
391 return Ty->isByteTy();
392 // We don't check elements recursively.
393 case StorageKind::Aggregate:
394 return Ty->isAggregateType() || Ty->isVectorTy();
395 }
396 llvm_unreachable("Unhandled storage kind.");
397 }
398
399 const APInt &asInteger() const {
400 assert(Kind == StorageKind::Integer && "Expect an integer value");
401 return IntVal;
402 }
403
404 const APFloat &asFloat() const {
405 assert(Kind == StorageKind::Float && "Expect a float value");
406 return FloatVal;
407 }
408
409 const Pointer &asPointer() const {
410 assert(Kind == StorageKind::Pointer && "Expect a pointer value");
411 return PtrVal;
412 }
413
414 const ByteValue &asByte() const {
415 assert(Kind == StorageKind::Byte && "Expect a byte value");
416 return ByteVal;
417 }
418
419 ByteValue &asMutableByte() {
420 assert(Kind == StorageKind::Byte && "Expect a byte value");
421 return ByteVal;
422 }
423
424 const std::vector<AnyValue> &asAggregate() const {
425 assert(Kind == StorageKind::Aggregate &&
426 "Expect an aggregate/vector value");
427 return AggVal;
428 }
429
430 std::vector<AnyValue> &asAggregate() {
431 assert(Kind == StorageKind::Aggregate &&
432 "Expect an aggregate/vector value");
433 return AggVal;
434 }
435
436 // Helper function for C++ 17 structured bindings.
437 template <size_t I> const AnyValue &get() const {
438 assert(Kind == StorageKind::Aggregate &&
439 "Expect an aggregate/vector value");
440 assert(I < AggVal.size() && "Index out of bounds");
441 return AggVal[I];
442 }
443
444 BooleanKind asBoolean() const {
445 if (isPoison())
446 return BooleanKind::Poison;
447 return asInteger().isZero() ? BooleanKind::False : BooleanKind::True;
448 }
449};
450
451class AnyValuePrinter {
452 Context &Ctx;
453 raw_ostream &OS;
454
455public:
456 AnyValuePrinter(Context &Ctx, raw_ostream &OS) : Ctx(Ctx), OS(OS) {}
457 AnyValuePrinter &operator<<(const AnyValue &V) {
458 V.print(Ctx, OS);
459 return *this;
460 }
461 template <typename T> AnyValuePrinter &operator<<(const T &Val) {
462 OS << Val;
463 return *this;
464 }
465 operator raw_ostream &() { return OS; }
466};
467
468inline raw_ostream &operator<<(raw_ostream &OS, const Pointer &P) {
469 P.print(OS);
470 return OS;
471}
472
473inline AnyValue addNoWrap(const APInt &LHS, const APInt &RHS, bool HasNSW,
474 bool HasNUW) {
475 APInt Res = LHS + RHS;
476 if (HasNUW && Res.ult(RHS))
477 return AnyValue::poison();
478 if (HasNSW && LHS.isNonNegative() == RHS.isNonNegative() &&
479 LHS.isNonNegative() != Res.isNonNegative())
480 return AnyValue::poison();
481 return Res;
482}
483
484inline AnyValue subNoWrap(const APInt &LHS, const APInt &RHS, bool HasNSW,
485 bool HasNUW) {
486 APInt Res = LHS - RHS;
487 if (HasNUW && Res.ugt(RHS: LHS))
488 return AnyValue::poison();
489 if (HasNSW && LHS.isNonNegative() != RHS.isNonNegative() &&
490 LHS.isNonNegative() != Res.isNonNegative())
491 return AnyValue::poison();
492 return Res;
493}
494
495inline AnyValue mulNoWrap(const APInt &LHS, const APInt &RHS, bool HasNSW,
496 bool HasNUW) {
497 bool Overflow = false;
498 APInt Res = LHS.smul_ov(RHS, Overflow);
499 if (HasNSW && Overflow)
500 return AnyValue::poison();
501 if (HasNUW) {
502 (void)LHS.umul_ov(RHS, Overflow);
503 if (Overflow)
504 return AnyValue::poison();
505 }
506 return Res;
507}
508
509} // namespace llvm::ubi
510
511#endif
512