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 /// Use getPoisonValue unless you know the scalar type is integer/fp/ptr!
325 static AnyValue poison() { return AnyValue(PoisonTag{}); }
326 static AnyValue boolean(bool Val) { return AnyValue(APInt(1, Val)); }
327 static AnyValue getPoisonValue(Context &Ctx, Type *Ty);
328 static AnyValue getNullValue(Context &Ctx, Type *Ty);
329 static AnyValue getVectorSplat(const AnyValue &Scalar, size_t NumElements);
330
331 bool isNone() const { return Kind == StorageKind::None; }
332 bool isPoison() const { return Kind == StorageKind::Poison; }
333 bool isInteger() const { return Kind == StorageKind::Integer; }
334 bool isFloat() const { return Kind == StorageKind::Float; }
335 bool isPointer() const { return Kind == StorageKind::Pointer; }
336 bool isByte() const { return Kind == StorageKind::Byte; }
337 bool isAggregate() const { return Kind == StorageKind::Aggregate; }
338
339 bool isCompatibleWith(Type *Ty) const {
340 switch (Kind) {
341 case StorageKind::None:
342 return Ty->isVoidTy();
343 case StorageKind::Poison:
344 return Ty->isFloatingPointTy() || Ty->isIntegerTy() || Ty->isPointerTy();
345 case StorageKind::Integer:
346 return Ty->isIntegerTy();
347 case StorageKind::Float:
348 return Ty->isFloatingPointTy();
349 case StorageKind::Pointer:
350 return Ty->isPointerTy();
351 case StorageKind::Byte:
352 return Ty->isByteTy();
353 // We don't check elements recursively.
354 case StorageKind::Aggregate:
355 return Ty->isAggregateType() || Ty->isVectorTy();
356 }
357 llvm_unreachable("Unhandled storage kind.");
358 }
359
360 const APInt &asInteger() const {
361 assert(Kind == StorageKind::Integer && "Expect an integer value");
362 return IntVal;
363 }
364
365 const APFloat &asFloat() const {
366 assert(Kind == StorageKind::Float && "Expect a float value");
367 return FloatVal;
368 }
369
370 const Pointer &asPointer() const {
371 assert(Kind == StorageKind::Pointer && "Expect a pointer value");
372 return PtrVal;
373 }
374
375 const ByteValue &asByte() const {
376 assert(Kind == StorageKind::Byte && "Expect a byte value");
377 return ByteVal;
378 }
379
380 ByteValue &asMutableByte() {
381 assert(Kind == StorageKind::Byte && "Expect a byte value");
382 return ByteVal;
383 }
384
385 const std::vector<AnyValue> &asAggregate() const {
386 assert(Kind == StorageKind::Aggregate &&
387 "Expect an aggregate/vector value");
388 return AggVal;
389 }
390
391 std::vector<AnyValue> &asAggregate() {
392 assert(Kind == StorageKind::Aggregate &&
393 "Expect an aggregate/vector value");
394 return AggVal;
395 }
396
397 // Helper function for C++ 17 structured bindings.
398 template <size_t I> const AnyValue &get() const {
399 assert(Kind == StorageKind::Aggregate &&
400 "Expect an aggregate/vector value");
401 assert(I < AggVal.size() && "Index out of bounds");
402 return AggVal[I];
403 }
404
405 BooleanKind asBoolean() const {
406 if (isPoison())
407 return BooleanKind::Poison;
408 return asInteger().isZero() ? BooleanKind::False : BooleanKind::True;
409 }
410};
411
412class AnyValuePrinter {
413 Context &Ctx;
414 raw_ostream &OS;
415
416public:
417 AnyValuePrinter(Context &Ctx, raw_ostream &OS) : Ctx(Ctx), OS(OS) {}
418 AnyValuePrinter &operator<<(const AnyValue &V) {
419 V.print(Ctx, OS);
420 return *this;
421 }
422 template <typename T> AnyValuePrinter &operator<<(const T &Val) {
423 OS << Val;
424 return *this;
425 }
426 operator raw_ostream &() { return OS; }
427};
428
429inline raw_ostream &operator<<(raw_ostream &OS, const Pointer &P) {
430 P.print(OS);
431 return OS;
432}
433
434inline AnyValue addNoWrap(const APInt &LHS, const APInt &RHS, bool HasNSW,
435 bool HasNUW) {
436 APInt Res = LHS + RHS;
437 if (HasNUW && Res.ult(RHS))
438 return AnyValue::poison();
439 if (HasNSW && LHS.isNonNegative() == RHS.isNonNegative() &&
440 LHS.isNonNegative() != Res.isNonNegative())
441 return AnyValue::poison();
442 return Res;
443}
444
445inline AnyValue subNoWrap(const APInt &LHS, const APInt &RHS, bool HasNSW,
446 bool HasNUW) {
447 APInt Res = LHS - RHS;
448 if (HasNUW && Res.ugt(RHS: LHS))
449 return AnyValue::poison();
450 if (HasNSW && LHS.isNonNegative() != RHS.isNonNegative() &&
451 LHS.isNonNegative() != Res.isNonNegative())
452 return AnyValue::poison();
453 return Res;
454}
455
456inline AnyValue mulNoWrap(const APInt &LHS, const APInt &RHS, bool HasNSW,
457 bool HasNUW) {
458 bool Overflow = false;
459 APInt Res = LHS.smul_ov(RHS, Overflow);
460 if (HasNSW && Overflow)
461 return AnyValue::poison();
462 if (HasNUW) {
463 (void)LHS.umul_ov(RHS, Overflow);
464 if (Overflow)
465 return AnyValue::poison();
466 }
467 return Res;
468}
469
470} // namespace llvm::ubi
471
472#endif
473