1//===--- Integral.h - Wrapper for numeric types for the VM ------*- 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// Defines the VM types and helpers operating on types.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_CLANG_AST_INTERP_INTEGRAL_H
14#define LLVM_CLANG_AST_INTERP_INTEGRAL_H
15
16#include "clang/AST/APValue.h"
17#include "clang/AST/CharUnits.h"
18#include "clang/AST/ComparisonCategories.h"
19#include "llvm/ADT/APSInt.h"
20#include "llvm/Support/MathExtras.h"
21#include "llvm/Support/raw_ostream.h"
22#include <cstddef>
23#include <cstdint>
24
25#include "Block.h"
26#include "Descriptor.h"
27#include "Primitives.h"
28
29namespace clang {
30namespace interp {
31
32using APInt = llvm::APInt;
33using APSInt = llvm::APSInt;
34
35template <bool Signed> class IntegralAP;
36
37// Helper structure to select the representation.
38template <unsigned Bits, bool Signed> struct Repr;
39template <> struct Repr<8, false> {
40 using Type = uint8_t;
41};
42template <> struct Repr<16, false> {
43 using Type = uint16_t;
44};
45template <> struct Repr<32, false> {
46 using Type = uint32_t;
47};
48template <> struct Repr<64, false> {
49 using Type = uint64_t;
50};
51template <> struct Repr<8, true> {
52 using Type = int8_t;
53};
54template <> struct Repr<16, true> {
55 using Type = int16_t;
56};
57template <> struct Repr<32, true> {
58 using Type = int32_t;
59};
60template <> struct Repr<64, true> {
61 using Type = int64_t;
62};
63
64/// Wrapper around numeric types.
65///
66/// These wrappers are required to shared an interface between APSint and
67/// builtin primitive numeral types, while optimising for storage and
68/// allowing methods operating on primitive type to compile to fast code.
69template <unsigned Bits, bool Signed> class Integral final {
70 static_assert(Bits >= 16);
71
72public:
73 // The primitive representing the integral.
74 using ReprT = typename Repr<Bits, Signed>::Type;
75
76private:
77 using OffsetT = intptr_t;
78 static_assert(std::is_trivially_copyable_v<ReprT>);
79 template <unsigned OtherBits, bool OtherSigned> friend class Integral;
80
81 IntegralKind Kind = IntegralKind::Number;
82 union {
83 ReprT V;
84 struct {
85 const void *P;
86 OffsetT Offset;
87 } Ptr;
88 struct {
89 const AddrLabelExpr *L1;
90 const AddrLabelExpr *L2;
91 } AddrLabelDiff;
92 };
93
94 /// Primitive representing limits.
95 static const auto Min = std::numeric_limits<ReprT>::min();
96 static const auto Max = std::numeric_limits<ReprT>::max();
97
98 /// Construct an integral from anything that is convertible to storage.
99 template <typename T> explicit Integral(T V) : V(V) {}
100 template <typename T>
101 explicit Integral(IntegralKind Kind, T V) : Kind(Kind), V(V) {}
102
103public:
104 using AsUnsigned = Integral<Bits, false>;
105
106 /// Zero-initializes an integral.
107 Integral() : V(0) {}
108
109 /// Constructs an integral from another integral.
110 template <unsigned SrcBits, bool SrcSign>
111 explicit Integral(Integral<SrcBits, SrcSign> V) : Kind(V.Kind), V(V) {}
112
113 /// Pointer integral of the given kind.
114 explicit Integral(IntegralKind Kind, const void *P, OffsetT Offset = 0)
115 : Kind(Kind) {
116 Ptr.P = P;
117 Ptr.Offset = Offset;
118 }
119
120 /// AddrLabelDiff integral.
121 explicit Integral(const AddrLabelExpr *P1, const AddrLabelExpr *P2)
122 : Kind(IntegralKind::AddrLabelDiff) {
123 AddrLabelDiff.L1 = P1;
124 AddrLabelDiff.L2 = P2;
125 }
126
127 IntegralKind getKind() const { return Kind; }
128 bool isNumber() const { return Kind == IntegralKind::Number; }
129 const void *getPtr() const {
130 assert(!isNumber());
131 assert(Kind != IntegralKind::AddrLabelDiff);
132 return Ptr.P;
133 }
134 ReprT getOffset() const {
135 assert(!isNumber());
136 assert(Kind != IntegralKind::AddrLabelDiff);
137 return Ptr.Offset;
138 }
139 const AddrLabelExpr *getLabel1() const {
140 assert(Kind == IntegralKind::AddrLabelDiff);
141 return AddrLabelDiff.L1;
142 }
143 const AddrLabelExpr *getLabel2() const {
144 assert(Kind == IntegralKind::AddrLabelDiff);
145 return AddrLabelDiff.L2;
146 }
147
148 /// Construct an integral from a value based on signedness.
149 explicit Integral(const APSInt &V)
150 : V(V.isSigned() ? V.getSExtValue() : V.getZExtValue()) {}
151
152 bool operator<(Integral RHS) const { return V < RHS.V; }
153 bool operator>(Integral RHS) const { return V > RHS.V; }
154 bool operator<=(Integral RHS) const { return V <= RHS.V; }
155 bool operator>=(Integral RHS) const { return V >= RHS.V; }
156 bool operator==(Integral RHS) const { return V == RHS.V; }
157 bool operator!=(Integral RHS) const { return V != RHS.V; }
158 bool operator>=(unsigned RHS) const {
159 return static_cast<unsigned>(V) >= RHS;
160 }
161
162 bool operator>(unsigned RHS) const {
163 return V >= 0 && static_cast<unsigned>(V) > RHS;
164 }
165
166 Integral operator-() const { return Integral(-V); }
167 Integral operator-(const Integral &Other) const {
168 return Integral(V - Other.V);
169 }
170 Integral operator~() const { return Integral(~V); }
171
172 template <unsigned DstBits, bool DstSign>
173 explicit operator Integral<DstBits, DstSign>() const {
174 return Integral<DstBits, DstSign>(Kind, V);
175 }
176
177 template <typename Ty, typename = std::enable_if_t<std::is_integral_v<Ty>>>
178 explicit operator Ty() const {
179 return V;
180 }
181
182 APSInt toAPSInt() const {
183 assert(isNumber());
184 return APSInt(APInt(Bits, static_cast<uint64_t>(V), Signed), !Signed);
185 }
186
187 APSInt toAPSInt(unsigned BitWidth) const {
188 return APSInt(toAPInt(BitWidth), !Signed);
189 }
190
191 APInt toAPInt(unsigned BitWidth) const {
192 assert(isNumber());
193 if constexpr (Signed)
194 return APInt(Bits, static_cast<uint64_t>(V), Signed)
195 .sextOrTrunc(width: BitWidth);
196 else
197 return APInt(Bits, static_cast<uint64_t>(V), Signed)
198 .zextOrTrunc(width: BitWidth);
199 }
200
201 APValue toAPValue(const ASTContext &) const {
202 switch (Kind) {
203 case IntegralKind::Address: {
204 return APValue((const ValueDecl *)Ptr.P,
205 CharUnits::fromQuantity(Ptr.Offset),
206 APValue::NoLValuePath{});
207 }
208 case IntegralKind::ExprAddress: {
209 return APValue((const Expr *)Ptr.P, CharUnits::fromQuantity(Ptr.Offset),
210 APValue::NoLValuePath{});
211 }
212 case IntegralKind::LabelAddress: {
213 return APValue((const Expr *)Ptr.P, CharUnits::Zero(),
214 APValue::NoLValuePath{});
215 }
216 case IntegralKind::BlockAddress: {
217 const Block *B = reinterpret_cast<const Block *>(Ptr.P);
218 const Descriptor *D = B->getDescriptor();
219 if (const Expr *E = D->asExpr())
220 return APValue(E, CharUnits::Zero(), APValue::NoLValuePath{});
221
222 return APValue(D->asValueDecl(), CharUnits::Zero(),
223 APValue::NoLValuePath{});
224 }
225 case IntegralKind::FunctionAddress: {
226 return APValue((const FunctionDecl *)Ptr.P,
227 CharUnits::fromQuantity(Ptr.Offset),
228 APValue::NoLValuePath{});
229 }
230 case IntegralKind::AddrLabelDiff: {
231 return APValue(AddrLabelDiff.L1, AddrLabelDiff.L2);
232 }
233 case IntegralKind::Number:
234 return APValue(toAPSInt());
235 }
236 llvm_unreachable("Unhandled IntegralKind");
237 }
238
239 Integral<Bits, false> toUnsigned() const {
240 return Integral<Bits, false>(*this);
241 }
242
243 constexpr static unsigned bitWidth() { return Bits; }
244 constexpr static bool isSigned() { return Signed; }
245
246 bool isZero() const { return !V; }
247 bool isMin() const { return *this == min(NumBits: bitWidth()); }
248 bool isMinusOne() const { return Signed && V == ReprT(-1); }
249 bool isNegative() const { return V < ReprT(0); }
250 bool isPositive() const { return !isNegative(); }
251
252 ComparisonCategoryResult compare(const Integral &RHS) const {
253 return Compare(V, RHS.V);
254 }
255
256 void bitcastToMemory(std::byte *Dest) const {
257 assert(isNumber());
258 std::memcpy(dest: Dest, src: &V, n: sizeof(V));
259 }
260
261 static Integral bitcastFromMemory(const std::byte *Src, unsigned BitWidth) {
262 assert(BitWidth == sizeof(ReprT) * 8);
263 ReprT V;
264
265 std::memcpy(dest: &V, src: Src, n: sizeof(ReprT));
266 return Integral(V);
267 }
268
269 std::string toDiagnosticString(const ASTContext &Ctx) const {
270 std::string NameStr;
271 llvm::raw_string_ostream OS(NameStr);
272 OS << V;
273 return NameStr;
274 }
275
276 unsigned countLeadingZeros() const {
277 assert(isNumber());
278 if constexpr (!Signed)
279 return llvm::countl_zero<ReprT>(V);
280 if (isPositive())
281 return llvm::countl_zero<typename AsUnsigned::ReprT>(
282 static_cast<typename AsUnsigned::ReprT>(V));
283 llvm_unreachable("Don't call countLeadingZeros() on negative values.");
284 }
285
286 unsigned getActiveBits() const {
287 assert(isNumber());
288 return Bits - countLeadingZeros();
289 }
290
291 Integral truncate(unsigned TruncBits) const {
292 assert(TruncBits >= 1);
293 if (TruncBits >= Bits)
294 return *this;
295 const ReprT BitMask = (ReprT(1) << ReprT(TruncBits)) - 1;
296 const ReprT SignBit = ReprT(1) << (TruncBits - 1);
297 const ReprT ExtMask = ~BitMask;
298 return Integral((V & BitMask) | (Signed && (V & SignBit) ? ExtMask : 0));
299 }
300
301 void print(llvm::raw_ostream &OS) const {
302 switch (Kind) {
303 case IntegralKind::Number:
304 OS << V;
305 break;
306 case IntegralKind::AddrLabelDiff:
307 OS << AddrLabelDiff.L1 << " - " << AddrLabelDiff.L2 << " (AddrLabelDiff)";
308 break;
309 case IntegralKind::Address:
310 OS << Ptr.P << " + " << Ptr.Offset << " (Address)";
311 break;
312 case IntegralKind::ExprAddress:
313 OS << Ptr.P << " + " << Ptr.Offset << " (ExprAddress)";
314 break;
315 case IntegralKind::BlockAddress:
316 OS << Ptr.P << " + " << Ptr.Offset << " (BlockAddress)";
317 break;
318 case IntegralKind::LabelAddress:
319 OS << Ptr.P << " + " << Ptr.Offset << " (LabelAddress)";
320 break;
321 case IntegralKind::FunctionAddress:
322 OS << Ptr.P << " + " << Ptr.Offset << " (FunctionAddress)";
323 }
324 }
325
326 static Integral min(unsigned NumBits) { return Integral(Min); }
327 static Integral max(unsigned NumBits) { return Integral(Max); }
328 static Integral zero(unsigned BitWidth = 0) { return from(0); }
329
330 template <typename ValT>
331 static std::enable_if_t<!std::is_same_v<ValT, IntegralKind>, Integral>
332 from(ValT V, unsigned NumBits = 0) {
333 if constexpr (std::is_integral_v<ValT>)
334 return Integral(V);
335 else
336 return Integral(static_cast<Integral::ReprT>(V));
337 }
338
339 template <unsigned SrcBits, bool SrcSign>
340 static std::enable_if_t<SrcBits != 0, Integral>
341 from(Integral<SrcBits, SrcSign> V) {
342 switch (V.Kind) {
343 case IntegralKind::Number:
344 return Integral(V.V);
345 case IntegralKind::AddrLabelDiff:
346 return Integral(V.getLabel1(), V.getLabel2());
347 case IntegralKind::Address:
348 case IntegralKind::ExprAddress:
349 case IntegralKind::BlockAddress:
350 case IntegralKind::LabelAddress:
351 case IntegralKind::FunctionAddress:
352 return Integral(V.getKind(), V.getPtr(), V.getOffset());
353 }
354 llvm_unreachable("Unhandled IntegralKind");
355 }
356
357 template <typename T> static Integral from(IntegralKind Kind, T V) {
358 return Integral(Kind, V);
359 }
360
361 static bool increment(Integral A, Integral *R) {
362 assert(A.isNumber());
363 return add(A, B: Integral(ReprT(1)), OpBits: A.bitWidth(), R);
364 }
365
366 static bool decrement(Integral A, Integral *R) {
367 assert(A.isNumber());
368 return sub(A, B: Integral(ReprT(1)), OpBits: A.bitWidth(), R);
369 }
370
371 static bool add(Integral A, Integral B, unsigned OpBits, Integral *R) {
372 assert(A.isNumber() && B.isNumber());
373 return CheckAddUB(A.V, B.V, R->V);
374 }
375
376 static bool sub(Integral A, Integral B, unsigned OpBits, Integral *R) {
377 assert(A.isNumber() && B.isNumber());
378 return CheckSubUB(A.V, B.V, R->V);
379 }
380
381 static bool mul(Integral A, Integral B, unsigned OpBits, Integral *R) {
382 assert(A.isNumber() && B.isNumber());
383 return CheckMulUB(A.V, B.V, R->V);
384 }
385
386 static bool rem(Integral A, Integral B, unsigned OpBits, Integral *R) {
387 assert(A.isNumber() && B.isNumber());
388 *R = Integral(A.V % B.V);
389 return false;
390 }
391
392 static bool div(Integral A, Integral B, unsigned OpBits, Integral *R) {
393 assert(A.isNumber() && B.isNumber());
394 *R = Integral(A.V / B.V);
395 return false;
396 }
397
398 static bool bitAnd(Integral A, Integral B, unsigned OpBits, Integral *R) {
399 assert(A.isNumber() && B.isNumber());
400 *R = Integral(A.V & B.V);
401 return false;
402 }
403
404 static bool bitOr(Integral A, Integral B, unsigned OpBits, Integral *R) {
405 assert(A.isNumber() && B.isNumber());
406 *R = Integral(A.V | B.V);
407 return false;
408 }
409
410 static bool bitXor(Integral A, Integral B, unsigned OpBits, Integral *R) {
411 assert(A.isNumber() && B.isNumber());
412 *R = Integral(A.V ^ B.V);
413 return false;
414 }
415
416 static bool neg(Integral A, Integral *R) {
417 if (Signed && A.isMin())
418 return true;
419
420 *R = -A;
421 return false;
422 }
423
424 static bool comp(Integral A, Integral *R) {
425 *R = Integral(~A.V);
426 return false;
427 }
428
429 template <unsigned RHSBits, bool RHSSign>
430 static void shiftLeft(const Integral A, const Integral<RHSBits, RHSSign> B,
431 unsigned OpBits, Integral *R) {
432 *R = Integral::from(A.V << B.V, OpBits);
433 }
434
435 template <unsigned RHSBits, bool RHSSign>
436 static void shiftRight(const Integral A, const Integral<RHSBits, RHSSign> B,
437 unsigned OpBits, Integral *R) {
438 *R = Integral::from(A.V >> B.V, OpBits);
439 }
440};
441
442template <unsigned Bits, bool Signed>
443llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, Integral<Bits, Signed> I) {
444 I.print(OS);
445 return OS;
446}
447
448} // namespace interp
449} // namespace clang
450
451#endif
452