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 bool areHighBitsZExtd(uint8_t BitsFrom) const {
121 uint8_t Mask = static_cast<uint8_t>((~0U) << BitsFrom);
122 return (ConcreteMask & Mask) == Mask && (Value & Mask) == 0 &&
123 (TagMask & Mask) == 0;
124 }
125};
126
127enum class StorageKind {
128 Integer,
129 Float,
130 Pointer,
131 Byte,
132 Poison,
133 None, // Placeholder for void type
134 Aggregate, // Struct, Array or Vector
135};
136
137/// Tri-state boolean value.
138enum class BooleanKind { False, True, Poison };
139
140/// A set of previously exposed provenances. It is originally yielded by
141/// inttoptr, and shared by pointers derived from the result.
142///
143/// Each capability check may invalidate some provenances. If we cannot
144/// pick one, it is UB. That is, from the angelic non-determinism view,
145/// we cannot pick a provenance to make the program reach this point.
146///
147/// For efficiency, this class has different forms in two stages:
148/// 1. Before any memory access is performed, ActiveMask is set to zero and
149/// Generation represents the global generation number of the snapshot.
150/// 2. After a memory access is performed, we can determine exactly one memory
151/// object to be accessed (address ranges are distinct). In this case,
152/// BaseAddress is set and ActiveMask is non-zero. ActiveMask represents the
153/// validity of the first N exposed provenances associated with the memory
154/// object. The bitwidth N is the number of provenances in the list with
155/// List[I].Generation <= WildcardProvenance::Generation (The generation field
156/// in the list is monotonically increasing). That is, we can only access
157/// through exposed provenances before inttoptr executes. Note that if
158/// ActiveMask becomes zero again, UB must be triggered.
159class WildcardProvenance : public RefCountedBase<WildcardProvenance> {
160 APInt ActiveMask;
161 union {
162 uint64_t Generation;
163 uint64_t BaseAddress;
164 };
165
166 friend class Context;
167
168public:
169 explicit WildcardProvenance(uint64_t Generation)
170 : ActiveMask(), Generation(Generation) {}
171};
172
173/// Components of a pointer excluding address. They are shared between pointer
174/// values, as most of operations don't change the provenance.
175/// Each node will be assigned a unique, pointer-sized tag, which is used to
176/// represent the pointer in the memory.
177/// The provenance can be either concrete or wildcard, as determined by the
178/// cases below:
179/// Obj Wildcard State
180/// Null Null Invalid
181/// Null NonNull Wildcard
182/// NonNull Null Concrete
183/// NonNull NonNull Wildcard (associated with a specific MO)
184class Provenance : public RefCountedBase<Provenance> {
185 // TODO: store reference to the provenance of the pointer it is derived from
186
187 // The underlying memory object. It can be null for invalid or dangling
188 // pointers. Besides, for pointers with wildcard provenance, it can be null
189 // until the memory object is resolved by gep inbounds.
190 IntrusiveRefCntPtr<MemoryObject> Obj;
191
192 // A tag is a randomly generated unique identifier to recover the provenance
193 // of a pointer. The length of tag is equal to the store size of the pointer
194 // type, in bits. It may produce false negatives in some corner cases. But in
195 // real practice the false negative rate should be negligible.
196 // A zero tag is invalid.
197 APInt Tag;
198
199 // Null if it is concrete.
200 IntrusiveRefCntPtr<WildcardProvenance> Wildcard;
201
202 // TODO: modeling nofree
203 // TODO: modeling captures
204 // TODO: modeling inrange(Start, End) attribute
205
206 const APInt &getTag() const { return Tag; }
207 void setTag(const APInt &T) { Tag = T; }
208
209 friend class Context;
210
211public:
212 Provenance(IntrusiveRefCntPtr<MemoryObject> Obj) : Obj(std::move(Obj)) {}
213 static IntrusiveRefCntPtr<Provenance> nullary();
214 IntrusiveRefCntPtr<Provenance> getWithKnownMemoryObject(MemoryObject &Obj);
215 MemoryObject *getMemoryObject() const { return Obj.get(); }
216 bool isWildcard() const { return Wildcard != nullptr; }
217};
218
219class Pointer {
220 // The provenance of the pointer.
221 IntrusiveRefCntPtr<Provenance> Prov;
222 // The address of the pointer. The bit width is determined by
223 // DataLayout::getPointerSizeInBits.
224 APInt Address;
225
226public:
227 explicit Pointer(const APInt &Address)
228 : Prov(Provenance::nullary()), Address(Address) {}
229 explicit Pointer(IntrusiveRefCntPtr<Provenance> Prov, const APInt &Address)
230 : Prov(std::move(Prov)), Address(Address) {
231 assert(this->Prov && "Invalid provenance.");
232 }
233 Pointer getWithNewAddr(const APInt &NewAddr) const {
234 return Pointer(Prov, NewAddr);
235 }
236 Pointer getWithNewProvenance(IntrusiveRefCntPtr<Provenance> NewProv) const {
237 return Pointer(NewProv, Address);
238 }
239 static AnyValue null(unsigned AS, const DataLayout &DL);
240 bool isNullPtr(unsigned AS, const DataLayout &DL) const;
241 void print(raw_ostream &OS) const;
242 const APInt &address() const { return Address; }
243 Provenance &provenance() const { return *Prov; }
244};
245
246/// Represents a scalar byte value. If the value is not byte-sized, the high
247/// bits are zero-padded.
248class ByteValue {
249 // The byte order is endianness-dependent.
250 std::vector<Byte> Val;
251 uint32_t BitWidth : 31;
252 uint32_t IsLittleEndian : 1;
253
254public:
255 ByteValue(const APInt &V, bool IsLittleEndian);
256 ByteValue(uint32_t BitWidth, ArrayRef<Byte> Val, bool IsLittleEndian,
257 bool ImplicitClearHighBits = false)
258 : ByteValue(BitWidth, std::vector<Byte>(Val), IsLittleEndian,
259 ImplicitClearHighBits) {}
260 ByteValue(uint32_t BitWidth, std::vector<Byte> Val, bool IsLittleEndian,
261 bool ImplicitClearHighBits = false)
262 : Val(std::move(Val)), BitWidth(BitWidth),
263 IsLittleEndian(IsLittleEndian) {
264 if (ImplicitClearHighBits && (BitWidth & 7) != 0) {
265 uint8_t Mask = static_cast<uint8_t>((~0U) << (BitWidth & 7));
266 if (IsLittleEndian)
267 this->Val.back().zeroBits(Mask);
268 else
269 this->Val.front().zeroBits(Mask);
270 }
271 assert(((BitWidth & 7) == 0 ||
272 ((IsLittleEndian ? this->Val.back() : this->Val.front())
273 .areHighBitsZExtd(BitWidth & 7))) &&
274 "The caller is responsible to zero high bits for non-byte-sized "
275 "values.");
276 }
277 ByteValue(const ByteValue &) = default;
278 ByteValue(ByteValue &&) = default;
279 ByteValue &operator=(const ByteValue &) = default;
280 ByteValue &operator=(ByteValue &&) = default;
281 ~ByteValue() = default;
282
283 static ByteValue zero(uint32_t BitWidth, bool IsLittleEndian);
284 static ByteValue poison(uint32_t BitWidth, bool IsLittleEndian);
285
286 uint32_t getBitWidth() const { return BitWidth; }
287 ArrayRef<Byte> bytes() const { return Val; }
288 MutableArrayRef<Byte> mutableBytes() { return Val; }
289 void print(Context &Ctx, raw_ostream &OS) const;
290};
291
292// Value representation for actual values of LLVM values.
293// We don't model undef values here (except for byte types).
294class [[nodiscard]] AnyValue {
295 StorageKind Kind;
296 union {
297 APInt IntVal;
298 APFloat FloatVal;
299 Pointer PtrVal;
300 ByteValue ByteVal;
301 std::vector<AnyValue> AggVal;
302 };
303
304 struct PoisonTag {};
305 void destroy();
306
307public:
308 AnyValue() : Kind(StorageKind::None) {}
309 explicit AnyValue(PoisonTag) : Kind(StorageKind::Poison) {}
310 AnyValue(APInt Val) : Kind(StorageKind::Integer), IntVal(std::move(Val)) {}
311 AnyValue(APFloat Val) : Kind(StorageKind::Float), FloatVal(std::move(Val)) {}
312 AnyValue(Pointer Val) : Kind(StorageKind::Pointer), PtrVal(std::move(Val)) {}
313 AnyValue(ByteValue Val) : Kind(StorageKind::Byte), ByteVal(std::move(Val)) {}
314 AnyValue(std::vector<AnyValue> Val)
315 : Kind(StorageKind::Aggregate), AggVal(std::move(Val)) {}
316 AnyValue(const AnyValue &Other);
317 AnyValue(AnyValue &&Other);
318 AnyValue &operator=(const AnyValue &);
319 AnyValue &operator=(AnyValue &&);
320 ~AnyValue() { destroy(); }
321
322 void print(Context &Ctx, raw_ostream &OS) const;
323
324 static AnyValue poison() { return AnyValue(PoisonTag{}); }
325 static AnyValue boolean(bool Val) { return AnyValue(APInt(1, Val)); }
326 static AnyValue getPoisonValue(Context &Ctx, Type *Ty);
327 static AnyValue getNullValue(Context &Ctx, Type *Ty);
328 static AnyValue getVectorSplat(const AnyValue &Scalar, size_t NumElements);
329
330 bool isNone() const { return Kind == StorageKind::None; }
331 bool isPoison() const { return Kind == StorageKind::Poison; }
332 bool isInteger() const { return Kind == StorageKind::Integer; }
333 bool isFloat() const { return Kind == StorageKind::Float; }
334 bool isPointer() const { return Kind == StorageKind::Pointer; }
335 bool isByte() const { return Kind == StorageKind::Byte; }
336 bool isAggregate() const { return Kind == StorageKind::Aggregate; }
337
338 bool isCompatibleWith(Type *Ty) const {
339 switch (Kind) {
340 case StorageKind::None:
341 return Ty->isVoidTy();
342 case StorageKind::Poison:
343 return Ty->isFloatingPointTy() || Ty->isIntegerTy() || Ty->isPointerTy();
344 case StorageKind::Integer:
345 return Ty->isIntegerTy();
346 case StorageKind::Float:
347 return Ty->isFloatingPointTy();
348 case StorageKind::Pointer:
349 return Ty->isPointerTy();
350 case StorageKind::Byte:
351 return Ty->isByteTy();
352 // We don't check elements recursively.
353 case StorageKind::Aggregate:
354 return Ty->isAggregateType() || Ty->isVectorTy();
355 }
356 llvm_unreachable("Unhandled storage kind.");
357 }
358
359 const APInt &asInteger() const {
360 assert(Kind == StorageKind::Integer && "Expect an integer value");
361 return IntVal;
362 }
363
364 const APFloat &asFloat() const {
365 assert(Kind == StorageKind::Float && "Expect a float value");
366 return FloatVal;
367 }
368
369 const Pointer &asPointer() const {
370 assert(Kind == StorageKind::Pointer && "Expect a pointer value");
371 return PtrVal;
372 }
373
374 const ByteValue &asByte() const {
375 assert(Kind == StorageKind::Byte && "Expect a byte value");
376 return ByteVal;
377 }
378
379 ByteValue &asMutableByte() {
380 assert(Kind == StorageKind::Byte && "Expect a byte value");
381 return ByteVal;
382 }
383
384 const std::vector<AnyValue> &asAggregate() const {
385 assert(Kind == StorageKind::Aggregate &&
386 "Expect an aggregate/vector value");
387 return AggVal;
388 }
389
390 std::vector<AnyValue> &asAggregate() {
391 assert(Kind == StorageKind::Aggregate &&
392 "Expect an aggregate/vector value");
393 return AggVal;
394 }
395
396 // Helper function for C++ 17 structured bindings.
397 template <size_t I> const AnyValue &get() const {
398 assert(Kind == StorageKind::Aggregate &&
399 "Expect an aggregate/vector value");
400 assert(I < AggVal.size() && "Index out of bounds");
401 return AggVal[I];
402 }
403
404 BooleanKind asBoolean() const {
405 if (isPoison())
406 return BooleanKind::Poison;
407 return asInteger().isZero() ? BooleanKind::False : BooleanKind::True;
408 }
409};
410
411class AnyValuePrinter {
412 Context &Ctx;
413 raw_ostream &OS;
414
415public:
416 AnyValuePrinter(Context &Ctx, raw_ostream &OS) : Ctx(Ctx), OS(OS) {}
417 AnyValuePrinter &operator<<(const AnyValue &V) {
418 V.print(Ctx, OS);
419 return *this;
420 }
421 template <typename T> AnyValuePrinter &operator<<(const T &Val) {
422 OS << Val;
423 return *this;
424 }
425 operator raw_ostream &() { return OS; }
426};
427
428inline raw_ostream &operator<<(raw_ostream &OS, const Pointer &P) {
429 P.print(OS);
430 return OS;
431}
432
433inline AnyValue addNoWrap(const APInt &LHS, const APInt &RHS, bool HasNSW,
434 bool HasNUW) {
435 APInt Res = LHS + RHS;
436 if (HasNUW && Res.ult(RHS))
437 return AnyValue::poison();
438 if (HasNSW && LHS.isNonNegative() == RHS.isNonNegative() &&
439 LHS.isNonNegative() != Res.isNonNegative())
440 return AnyValue::poison();
441 return Res;
442}
443
444inline AnyValue subNoWrap(const APInt &LHS, const APInt &RHS, bool HasNSW,
445 bool HasNUW) {
446 APInt Res = LHS - RHS;
447 if (HasNUW && Res.ugt(RHS: LHS))
448 return AnyValue::poison();
449 if (HasNSW && LHS.isNonNegative() != RHS.isNonNegative() &&
450 LHS.isNonNegative() != Res.isNonNegative())
451 return AnyValue::poison();
452 return Res;
453}
454
455inline AnyValue mulNoWrap(const APInt &LHS, const APInt &RHS, bool HasNSW,
456 bool HasNUW) {
457 bool Overflow = false;
458 APInt Res = LHS.smul_ov(RHS, Overflow);
459 if (HasNSW && Overflow)
460 return AnyValue::poison();
461 if (HasNUW) {
462 (void)LHS.umul_ov(RHS, Overflow);
463 if (Overflow)
464 return AnyValue::poison();
465 }
466 return Res;
467}
468
469} // namespace llvm::ubi
470
471#endif
472