1//===- Value.cpp - Value Representation 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 implements utility functions for the value representation.
10//
11//===----------------------------------------------------------------------===//
12
13#include "Value.h"
14#include "Context.h"
15#include "llvm/ADT/SmallString.h"
16
17namespace llvm::ubi {
18
19IntrusiveRefCntPtr<Provenance> Provenance::nullary() {
20 static IntrusiveRefCntPtr<Provenance> Instance =
21 makeIntrusiveRefCnt<Provenance>(A: nullptr);
22 return Instance;
23}
24
25IntrusiveRefCntPtr<Provenance>
26Provenance::getWithKnownMemoryObject(MemoryObject &KnownObj) {
27 assert(!Obj && Wildcard && "The memory object has been determined.");
28 auto Res = makeIntrusiveRefCnt<Provenance>(A&: *this);
29 Res->Obj = &KnownObj;
30 Res->Tag = APInt();
31 return Res;
32}
33
34void Pointer::print(raw_ostream &OS) const {
35 SmallString<32> AddrStr;
36 Address.toStringUnsigned(Str&: AddrStr, Radix: 16);
37 OS << "ptr 0x" << AddrStr << " [";
38 if (MemoryObject *Obj = Prov->getMemoryObject()) {
39 if (Obj->isIRGlobalValue())
40 OS << "@";
41 OS << Obj->getName();
42 if (Address != Obj->getAddress())
43 OS << " + " << (Address - Obj->getAddress());
44 MemoryObjectState State = Obj->getState();
45 if (State != MemoryObjectState::Alive)
46 OS << (State == MemoryObjectState::Dead ? " (dead)" : " (dangling)");
47 } else {
48 OS << (Prov->isWildcard() ? "wildcard" : "nullary");
49 }
50 // TODO: print provenance
51 OS << "]";
52}
53
54AnyValue Pointer::null(unsigned AS, const DataLayout &DL) {
55 return AnyValue(Pointer(Provenance::nullary(), DL.getNullPtrValue(AS)));
56}
57
58bool Pointer::isNullPtr(unsigned AS, const DataLayout &DL) const {
59 return Address == DL.getNullPtrValue(AS);
60}
61
62void AnyValue::print(Context &Ctx, raw_ostream &OS) const {
63 switch (Kind) {
64 case StorageKind::Integer:
65 if (IntVal.getBitWidth() == 1) {
66 OS << (IntVal.getBoolValue() ? "T" : "F");
67 break;
68 }
69 OS << "i" << IntVal.getBitWidth() << ' ' << IntVal;
70 break;
71 case StorageKind::Float: {
72 switch (APFloat::SemanticsToEnum(Sem: FloatVal.getSemantics())) {
73 default:
74 llvm_unreachable("invalid fltSemantics");
75 case APFloatBase::S_IEEEhalf:
76 OS << "half ";
77 break;
78 case APFloatBase::S_BFloat:
79 OS << "bfloat ";
80 break;
81 case APFloatBase::S_IEEEsingle:
82 OS << "float ";
83 break;
84 case APFloatBase::S_IEEEdouble:
85 OS << "double ";
86 break;
87 case APFloatBase::S_x87DoubleExtended:
88 OS << "x86_fp80 ";
89 break;
90 case APFloatBase::S_IEEEquad:
91 OS << "fp128 ";
92 break;
93 case APFloatBase::S_PPCDoubleDouble:
94 OS << "ppc_fp128 ";
95 break;
96 }
97 // We cannot reuse Value::print due to lack of LLVMContext here.
98 // Similar to writeAPFloatInternal, output the FP constant value in
99 // exponential notation if it is lossless, otherwise output it in
100 // hexadecimal notation.
101 SmallString<16> StrVal;
102 FloatVal.toString(Str&: StrVal, /*FormatPrecision=*/6, /*FormatMaxPadding=*/0,
103 /*TruncateZero=*/false);
104 if (APFloat(FloatVal.getSemantics(), StrVal).bitwiseIsEqual(RHS: FloatVal)) {
105 OS << StrVal;
106 } else {
107 StrVal.clear();
108 APInt Bits = FloatVal.bitcastToAPInt();
109 Bits.toStringUnsigned(Str&: StrVal, Radix: 16);
110 size_t MaxDigits = divideCeil(Numerator: Bits.getBitWidth(), Denominator: 4);
111 OS << "0x";
112 for (size_t Digits = StrVal.size(); Digits != MaxDigits; ++Digits)
113 OS << '0';
114 OS << StrVal;
115 }
116 break;
117 }
118 case StorageKind::Pointer:
119 PtrVal.print(OS);
120 break;
121 case StorageKind::Byte:
122 ByteVal.print(Ctx, OS);
123 break;
124 case StorageKind::Poison:
125 OS << "poison";
126 break;
127 case StorageKind::None:
128 OS << "none";
129 break;
130 case StorageKind::Aggregate:
131 OS << "{ ";
132 for (size_t I = 0, E = AggVal.size(); I != E; ++I) {
133 if (I != 0)
134 OS << ", ";
135 AggVal[I].print(Ctx, OS);
136 }
137 OS << " }";
138 break;
139 }
140}
141
142void AnyValue::destroy() {
143 switch (Kind) {
144 case StorageKind::Integer:
145 IntVal.~APInt();
146 break;
147 case StorageKind::Float:
148 FloatVal.~APFloat();
149 break;
150 case StorageKind::Pointer:
151 PtrVal.~Pointer();
152 break;
153 case StorageKind::Byte:
154 ByteVal.~ByteValue();
155 break;
156 case StorageKind::Poison:
157 case StorageKind::None:
158 break;
159 case StorageKind::Aggregate:
160 AggVal.~vector();
161 break;
162 }
163}
164
165AnyValue::AnyValue(const AnyValue &Other) : Kind(Other.Kind) {
166 switch (Other.Kind) {
167 case StorageKind::Integer:
168 new (&IntVal) APInt(Other.IntVal);
169 break;
170 case StorageKind::Float:
171 new (&FloatVal) APFloat(Other.FloatVal);
172 break;
173 case StorageKind::Pointer:
174 new (&PtrVal) Pointer(Other.PtrVal);
175 break;
176 case StorageKind::Byte:
177 new (&ByteVal) ByteValue(Other.ByteVal);
178 break;
179 case StorageKind::Poison:
180 case StorageKind::None:
181 break;
182 case StorageKind::Aggregate:
183 new (&AggVal) std::vector<AnyValue>(Other.AggVal);
184 break;
185 }
186}
187AnyValue::AnyValue(AnyValue &&Other) : Kind(Other.Kind) {
188 switch (Other.Kind) {
189 case StorageKind::Integer:
190 new (&IntVal) APInt(std::move(Other.IntVal));
191 break;
192 case StorageKind::Float:
193 new (&FloatVal) APFloat(std::move(Other.FloatVal));
194 break;
195 case StorageKind::Pointer:
196 new (&PtrVal) Pointer(std::move(Other.PtrVal));
197 break;
198 case StorageKind::Byte:
199 new (&ByteVal) ByteValue(std::move(Other.ByteVal));
200 break;
201 case StorageKind::Poison:
202 case StorageKind::None:
203 break;
204 case StorageKind::Aggregate:
205 new (&AggVal) std::vector<AnyValue>(std::move(Other.AggVal));
206 break;
207 }
208}
209
210AnyValue &AnyValue::operator=(const AnyValue &Other) {
211 if (&Other == this)
212 return *this;
213
214 destroy();
215 Kind = Other.Kind;
216 switch (Other.Kind) {
217 case StorageKind::Integer:
218 new (&IntVal) APInt(Other.IntVal);
219 break;
220 case StorageKind::Float:
221 new (&FloatVal) APFloat(Other.FloatVal);
222 break;
223 case StorageKind::Pointer:
224 new (&PtrVal) Pointer(Other.PtrVal);
225 break;
226 case StorageKind::Byte:
227 new (&ByteVal) ByteValue(Other.ByteVal);
228 break;
229 case StorageKind::Poison:
230 case StorageKind::None:
231 break;
232 case StorageKind::Aggregate:
233 new (&AggVal) std::vector<AnyValue>(Other.AggVal);
234 break;
235 }
236
237 return *this;
238}
239AnyValue &AnyValue::operator=(AnyValue &&Other) {
240 if (&Other == this)
241 return *this;
242 destroy();
243 Kind = Other.Kind;
244 switch (Other.Kind) {
245 case StorageKind::Integer:
246 new (&IntVal) APInt(std::move(Other.IntVal));
247 break;
248 case StorageKind::Float:
249 new (&FloatVal) APFloat(std::move(Other.FloatVal));
250 break;
251 case StorageKind::Pointer:
252 new (&PtrVal) Pointer(std::move(Other.PtrVal));
253 break;
254 case StorageKind::Byte:
255 new (&ByteVal) ByteValue(std::move(Other.ByteVal));
256 break;
257 case StorageKind::Poison:
258 case StorageKind::None:
259 break;
260 case StorageKind::Aggregate:
261 new (&AggVal) std::vector<AnyValue>(std::move(Other.AggVal));
262 break;
263 }
264
265 return *this;
266}
267
268AnyValue AnyValue::getPoisonValue(Context &Ctx, Type *Ty) {
269 if (Ty->isFloatingPointTy() || Ty->isIntegerTy() || Ty->isPointerTy())
270 return AnyValue::poison();
271 if (Ty->isByteTy())
272 return ByteValue::poison(BitWidth: Ty->getByteBitWidth(),
273 IsLittleEndian: Ctx.getDataLayout().isLittleEndian());
274 if (auto *VecTy = dyn_cast<VectorType>(Val: Ty)) {
275 uint32_t NumElements = Ctx.getEVL(EC: VecTy->getElementCount());
276 return AnyValue(std::vector<AnyValue>(
277 NumElements, getPoisonValue(Ctx, Ty: VecTy->getScalarType())));
278 }
279 if (auto *ArrTy = dyn_cast<ArrayType>(Val: Ty)) {
280 uint64_t NumElements = ArrTy->getNumElements();
281 return AnyValue(std::vector<AnyValue>(
282 NumElements, getPoisonValue(Ctx, Ty: ArrTy->getElementType())));
283 }
284 if (auto *StructTy = dyn_cast<StructType>(Val: Ty)) {
285 std::vector<AnyValue> Elements;
286 Elements.reserve(n: StructTy->getNumElements());
287 for (uint32_t I = 0, E = StructTy->getNumElements(); I != E; ++I)
288 Elements.push_back(x: getPoisonValue(Ctx, Ty: StructTy->getElementType(N: I)));
289 return AnyValue(std::move(Elements));
290 }
291 llvm_unreachable("Unsupported type");
292}
293AnyValue AnyValue::getNullValue(Context &Ctx, Type *Ty) {
294 if (Ty->isIntegerTy())
295 return AnyValue(APInt::getZero(numBits: Ty->getIntegerBitWidth()));
296 if (Ty->isFloatingPointTy())
297 return AnyValue(APFloat::getZero(Sem: Ty->getFltSemantics()));
298 if (Ty->isPointerTy())
299 return Pointer::null(AS: Ty->getPointerAddressSpace(), DL: Ctx.getDataLayout());
300 if (Ty->isByteTy())
301 return ByteValue::zero(BitWidth: Ty->getByteBitWidth(),
302 IsLittleEndian: Ctx.getDataLayout().isLittleEndian());
303 if (auto *VecTy = dyn_cast<VectorType>(Val: Ty)) {
304 uint32_t NumElements = Ctx.getEVL(EC: VecTy->getElementCount());
305 return AnyValue(std::vector<AnyValue>(
306 NumElements, getNullValue(Ctx, Ty: VecTy->getElementType())));
307 }
308 if (auto *ArrTy = dyn_cast<ArrayType>(Val: Ty)) {
309 uint64_t NumElements = ArrTy->getNumElements();
310 return AnyValue(std::vector<AnyValue>(
311 NumElements, getNullValue(Ctx, Ty: ArrTy->getElementType())));
312 }
313 if (auto *StructTy = dyn_cast<StructType>(Val: Ty)) {
314 std::vector<AnyValue> Elements;
315 Elements.reserve(n: StructTy->getNumElements());
316 for (uint32_t I = 0, E = StructTy->getNumElements(); I != E; ++I)
317 Elements.push_back(x: getNullValue(Ctx, Ty: StructTy->getElementType(N: I)));
318 return AnyValue(std::move(Elements));
319 }
320 llvm_unreachable("Unsupported type");
321}
322
323AnyValue AnyValue::getVectorSplat(const AnyValue &Scalar, size_t NumElements) {
324 assert(!Scalar.isAggregate() && !Scalar.isNone() && "Expect a scalar value");
325 return AnyValue(std::vector<AnyValue>(NumElements, Scalar));
326}
327
328ByteValue::ByteValue(const APInt &V, bool IsLittleEndian)
329 : BitWidth(V.getBitWidth()), IsLittleEndian(IsLittleEndian) {
330 Val.resize(new_size: divideCeil(Numerator: BitWidth, Denominator: 8));
331 MutableBytesView View(Val, IsLittleEndian);
332 for (uint32_t I = 0; I < BitWidth; I += 8)
333 View[I / 8] = Byte::concrete(Val: static_cast<uint8_t>(
334 V.extractBitsAsZExtValue(numBits: std::min(a: BitWidth - I, b: 8U), bitPosition: I)));
335}
336ByteValue ByteValue::zero(uint32_t BitWidth, bool IsLittleEndian) {
337 return ByteValue(
338 BitWidth, std::vector<Byte>(divideCeil(Numerator: BitWidth, Denominator: 8), Byte::concrete(Val: 0)),
339 IsLittleEndian);
340}
341
342ByteValue ByteValue::poison(uint32_t BitWidth, bool IsLittleEndian) {
343 return ByteValue(BitWidth,
344 std::vector<Byte>(divideCeil(Numerator: BitWidth, Denominator: 8), Byte::poison()),
345 IsLittleEndian, /*ImplicitClearHighBits=*/true);
346}
347
348void ByteValue::print(Context &Ctx, raw_ostream &OS) const {
349 OS << 'b' << BitWidth << ' ';
350
351 auto PrintByte = [&](const Byte &V) {
352 bool IsFullByte = (BitWidth & 7) == 0 ||
353 (IsLittleEndian ? &Val.back() : &Val.front()) != &V;
354 // Try to print a byte in short form
355 if (IsFullByte && V.ConcreteMask == 255 && V.TagMask == 0) {
356 // Concrete value without provenance.
357 OS << "0x" << hexdigit(X: V.Value >> 4) << hexdigit(X: V.Value & 15);
358 } else if (IsFullByte && V.ConcreteMask == 0) {
359 assert(V.Value == 0 && "Byte values don't contain undef bits.");
360 // Poison bytes.
361 OS << "0x!!";
362 } else {
363 uint32_t BitEnd = IsFullByte ? 8 : BitWidth & 7;
364 for (uint32_t I = 0; I != BitEnd; ++I) {
365 uint32_t Mask = 1U << (BitEnd - 1 - I);
366 if (V.ConcreteMask & Mask)
367 OS << (V.Value & Mask ? '1' : '0');
368 else {
369 assert((V.Value & Mask) == 0 &&
370 "Byte values don't contain undef bits.");
371 OS << '!';
372 }
373 }
374 assert((V.ConcreteMask & V.TagMask) == V.TagMask);
375 if (V.TagMask) {
376 // Print tags if available.
377 OS << '(';
378 for (uint32_t I = 0; I != BitEnd; ++I) {
379 uint32_t Mask = 1U << (BitEnd - 1 - I);
380 if (V.TagMask & Mask)
381 OS << (V.TagValue & Mask ? '1' : '0');
382 else
383 OS << '!';
384 }
385 OS << ')';
386 }
387 }
388 OS << ' ';
389 };
390
391 auto &DL = Ctx.getDataLayout();
392 unsigned PtrWidthForAS0 = DL.getPointerSizeInBits(AS: 0);
393 Type *PtrTy = PointerType::getUnqual(C&: Ctx.getContext());
394
395 if (PtrWidthForAS0 % 8 == 0 && BitWidth % PtrWidthForAS0 == 0) {
396 // Try to treat the bytes value as an array of pointers in address space 0.
397 unsigned PtrSize = PtrWidthForAS0 / 8;
398 for (size_t I = 0, E = Val.size(); I != E; I += PtrSize) {
399 ArrayRef<Byte> Slice = ArrayRef(Val).slice(N: I, M: PtrSize);
400 if (all_of(Range&: Slice, P: [](const Byte &V) {
401 assert((V.ConcreteMask & V.TagMask) == V.TagMask);
402 return V.TagMask == 255;
403 })) {
404 AnyValue Res = Ctx.fromBytes(Bytes: Slice, Ty: PtrTy);
405 if (Res.isPointer()) {
406 Res.asPointer().print(OS);
407 OS << ' ';
408 continue;
409 }
410 }
411
412 // Otherwise, fallback into bytes array
413 for (size_t J = 0; J != PtrSize; ++J)
414 PrintByte(Val[I + J]);
415 }
416 } else {
417 for (const Byte &V : Val)
418 PrintByte(V);
419 }
420}
421
422} // namespace llvm::ubi
423