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 "Descriptor.h"
26#include "InterpBlock.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::LabelAddress: {
209 return APValue((const Expr *)Ptr.P, CharUnits::Zero(),
210 APValue::NoLValuePath{});
211 }
212 case IntegralKind::BlockAddress: {
213 const Block *B = reinterpret_cast<const Block *>(Ptr.P);
214 const Descriptor *D = B->getDescriptor();
215 if (const Expr *E = D->asExpr())
216 return APValue(E, CharUnits::Zero(), APValue::NoLValuePath{});
217
218 return APValue(D->asValueDecl(), CharUnits::Zero(),
219 APValue::NoLValuePath{});
220 }
221 case IntegralKind::FunctionAddress: {
222 return APValue((const FunctionDecl *)Ptr.P,
223 CharUnits::fromQuantity(Ptr.Offset),
224 APValue::NoLValuePath{});
225 }
226 case IntegralKind::AddrLabelDiff: {
227 return APValue(AddrLabelDiff.L1, AddrLabelDiff.L2);
228 }
229 case IntegralKind::Number:
230 return APValue(toAPSInt());
231 }
232 llvm_unreachable("Unhandled IntegralKind");
233 }
234
235 Integral<Bits, false> toUnsigned() const {
236 return Integral<Bits, false>(*this);
237 }
238
239 constexpr static unsigned bitWidth() { return Bits; }
240 constexpr static bool isSigned() { return Signed; }
241
242 bool isZero() const { return !V; }
243 bool isMin() const { return *this == min(NumBits: bitWidth()); }
244 bool isMinusOne() const { return Signed && V == ReprT(-1); }
245 bool isNegative() const { return V < ReprT(0); }
246 bool isPositive() const { return !isNegative(); }
247
248 ComparisonCategoryResult compare(const Integral &RHS) const {
249 return Compare(V, RHS.V);
250 }
251
252 void bitcastToMemory(std::byte *Dest) const {
253 assert(isNumber());
254 std::memcpy(dest: Dest, src: &V, n: sizeof(V));
255 }
256
257 static Integral bitcastFromMemory(const std::byte *Src, unsigned BitWidth) {
258 assert(BitWidth == sizeof(ReprT) * 8);
259 ReprT V;
260
261 std::memcpy(dest: &V, src: Src, n: sizeof(ReprT));
262 return Integral(V);
263 }
264
265 std::string toDiagnosticString(const ASTContext &Ctx) const {
266 std::string NameStr;
267 llvm::raw_string_ostream OS(NameStr);
268 OS << V;
269 return NameStr;
270 }
271
272 unsigned countLeadingZeros() const {
273 assert(isNumber());
274 if constexpr (!Signed)
275 return llvm::countl_zero<ReprT>(V);
276 if (isPositive())
277 return llvm::countl_zero<typename AsUnsigned::ReprT>(
278 static_cast<typename AsUnsigned::ReprT>(V));
279 llvm_unreachable("Don't call countLeadingZeros() on negative values.");
280 }
281
282 Integral truncate(unsigned TruncBits) const {
283 assert(TruncBits >= 1);
284 if (TruncBits >= Bits)
285 return *this;
286 const ReprT BitMask = (ReprT(1) << ReprT(TruncBits)) - 1;
287 const ReprT SignBit = ReprT(1) << (TruncBits - 1);
288 const ReprT ExtMask = ~BitMask;
289 return Integral((V & BitMask) | (Signed && (V & SignBit) ? ExtMask : 0));
290 }
291
292 void print(llvm::raw_ostream &OS) const {
293 switch (Kind) {
294 case IntegralKind::Number:
295 OS << V;
296 break;
297 case IntegralKind::AddrLabelDiff:
298 OS << AddrLabelDiff.L1 << " - " << AddrLabelDiff.L2 << " (AddrLabelDiff)";
299 break;
300 case IntegralKind::Address:
301 OS << Ptr.P << " + " << Ptr.Offset << " (Address)";
302 break;
303 case IntegralKind::BlockAddress:
304 OS << Ptr.P << " + " << Ptr.Offset << " (BlockAddress)";
305 break;
306 case IntegralKind::LabelAddress:
307 OS << Ptr.P << " + " << Ptr.Offset << " (LabelAddress)";
308 break;
309 case IntegralKind::FunctionAddress:
310 OS << Ptr.P << " + " << Ptr.Offset << " (FunctionAddress)";
311 }
312 }
313
314 static Integral min(unsigned NumBits) { return Integral(Min); }
315 static Integral max(unsigned NumBits) { return Integral(Max); }
316 static Integral zero(unsigned BitWidth = 0) { return from(0); }
317
318 template <typename ValT>
319 static std::enable_if_t<!std::is_same_v<ValT, IntegralKind>, Integral>
320 from(ValT V, unsigned NumBits = 0) {
321 if constexpr (std::is_integral_v<ValT>)
322 return Integral(V);
323 else
324 return Integral(static_cast<Integral::ReprT>(V));
325 }
326
327 template <unsigned SrcBits, bool SrcSign>
328 static std::enable_if_t<SrcBits != 0, Integral>
329 from(Integral<SrcBits, SrcSign> V) {
330 switch (V.Kind) {
331 case IntegralKind::Number:
332 return Integral(V.V);
333 case IntegralKind::AddrLabelDiff:
334 return Integral(V.getLabel1(), V.getLabel2());
335 case IntegralKind::Address:
336 case IntegralKind::BlockAddress:
337 case IntegralKind::LabelAddress:
338 case IntegralKind::FunctionAddress:
339 return Integral(V.getKind(), V.getPtr(), V.getOffset());
340 }
341 llvm_unreachable("Unhandled IntegralKind");
342 }
343
344 template <typename T> static Integral from(IntegralKind Kind, T V) {
345 return Integral(Kind, V);
346 }
347
348 static bool increment(Integral A, Integral *R) {
349 assert(A.isNumber());
350 return add(A, B: Integral(ReprT(1)), OpBits: A.bitWidth(), R);
351 }
352
353 static bool decrement(Integral A, Integral *R) {
354 assert(A.isNumber());
355 return sub(A, B: Integral(ReprT(1)), OpBits: A.bitWidth(), R);
356 }
357
358 static bool add(Integral A, Integral B, unsigned OpBits, Integral *R) {
359 assert(A.isNumber() && B.isNumber());
360 return CheckAddUB(A.V, B.V, R->V);
361 }
362
363 static bool sub(Integral A, Integral B, unsigned OpBits, Integral *R) {
364 assert(A.isNumber() && B.isNumber());
365 return CheckSubUB(A.V, B.V, R->V);
366 }
367
368 static bool mul(Integral A, Integral B, unsigned OpBits, Integral *R) {
369 assert(A.isNumber() && B.isNumber());
370 return CheckMulUB(A.V, B.V, R->V);
371 }
372
373 static bool rem(Integral A, Integral B, unsigned OpBits, Integral *R) {
374 assert(A.isNumber() && B.isNumber());
375 *R = Integral(A.V % B.V);
376 return false;
377 }
378
379 static bool div(Integral A, Integral B, unsigned OpBits, Integral *R) {
380 assert(A.isNumber() && B.isNumber());
381 *R = Integral(A.V / B.V);
382 return false;
383 }
384
385 static bool bitAnd(Integral A, Integral B, unsigned OpBits, Integral *R) {
386 assert(A.isNumber() && B.isNumber());
387 *R = Integral(A.V & B.V);
388 return false;
389 }
390
391 static bool bitOr(Integral A, Integral B, unsigned OpBits, Integral *R) {
392 assert(A.isNumber() && B.isNumber());
393 *R = Integral(A.V | B.V);
394 return false;
395 }
396
397 static bool bitXor(Integral A, Integral B, unsigned OpBits, Integral *R) {
398 assert(A.isNumber() && B.isNumber());
399 *R = Integral(A.V ^ B.V);
400 return false;
401 }
402
403 static bool neg(Integral A, Integral *R) {
404 if (Signed && A.isMin())
405 return true;
406
407 *R = -A;
408 return false;
409 }
410
411 static bool comp(Integral A, Integral *R) {
412 *R = Integral(~A.V);
413 return false;
414 }
415
416 template <unsigned RHSBits, bool RHSSign>
417 static void shiftLeft(const Integral A, const Integral<RHSBits, RHSSign> B,
418 unsigned OpBits, Integral *R) {
419 *R = Integral::from(A.V << B.V, OpBits);
420 }
421
422 template <unsigned RHSBits, bool RHSSign>
423 static void shiftRight(const Integral A, const Integral<RHSBits, RHSSign> B,
424 unsigned OpBits, Integral *R) {
425 *R = Integral::from(A.V >> B.V, OpBits);
426 }
427};
428
429template <unsigned Bits, bool Signed>
430llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, Integral<Bits, Signed> I) {
431 I.print(OS);
432 return OS;
433}
434
435} // namespace interp
436} // namespace clang
437
438#endif
439