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/ComparisonCategories.h"
17 #include "clang/AST/APValue.h"
18 #include "llvm/ADT/APSInt.h"
19 #include "llvm/Support/MathExtras.h"
20 #include "llvm/Support/raw_ostream.h"
21 #include <cstddef>
22 #include <cstdint>
23 
24 #include "Primitives.h"
25 
26 namespace clang {
27 namespace interp {
28 
29 using APInt = llvm::APInt;
30 using APSInt = llvm::APSInt;
31 
32 // Helper structure to select the representation.
33 template <unsigned Bits, bool Signed> struct Repr;
34 template <> struct Repr<8, false> { using Type = uint8_t; };
35 template <> struct Repr<16, false> { using Type = uint16_t; };
36 template <> struct Repr<32, false> { using Type = uint32_t; };
37 template <> struct Repr<64, false> { using Type = uint64_t; };
38 template <> struct Repr<8, true> { using Type = int8_t; };
39 template <> struct Repr<16, true> { using Type = int16_t; };
40 template <> struct Repr<32, true> { using Type = int32_t; };
41 template <> struct Repr<64, true> { using Type = int64_t; };
42 
43 /// Wrapper around numeric types.
44 ///
45 /// These wrappers are required to shared an interface between APSint and
46 /// builtin primitive numeral types, while optimising for storage and
47 /// allowing methods operating on primitive type to compile to fast code.
48 template <unsigned Bits, bool Signed> class Integral final {
49 private:
50   template <unsigned OtherBits, bool OtherSigned> friend class Integral;
51 
52   // The primitive representing the integral.
53   using ReprT = typename Repr<Bits, Signed>::Type;
54   ReprT V;
55 
56   /// Primitive representing limits.
57   static const auto Min = std::numeric_limits<ReprT>::min();
58   static const auto Max = std::numeric_limits<ReprT>::max();
59 
60   /// Construct an integral from anything that is convertible to storage.
61   template <typename T> explicit Integral(T V) : V(V) {}
62 
63 public:
64   /// Zero-initializes an integral.
65   Integral() : V(0) {}
66 
67   /// Constructs an integral from another integral.
68   template <unsigned SrcBits, bool SrcSign>
69   explicit Integral(Integral<SrcBits, SrcSign> V) : V(V.V) {}
70 
71   /// Construct an integral from a value based on signedness.
72   explicit Integral(const APSInt &V)
73       : V(V.isSigned() ? V.getSExtValue() : V.getZExtValue()) {}
74 
75   bool operator<(Integral RHS) const { return V < RHS.V; }
76   bool operator>(Integral RHS) const { return V > RHS.V; }
77   bool operator<=(Integral RHS) const { return V <= RHS.V; }
78   bool operator>=(Integral RHS) const { return V >= RHS.V; }
79   bool operator==(Integral RHS) const { return V == RHS.V; }
80   bool operator!=(Integral RHS) const { return V != RHS.V; }
81 
82   bool operator>(unsigned RHS) const {
83     return V >= 0 && static_cast<unsigned>(V) > RHS;
84   }
85 
86   Integral operator-() const { return Integral(-V); }
87   Integral operator~() const { return Integral(~V); }
88 
89   template <unsigned DstBits, bool DstSign>
90   explicit operator Integral<DstBits, DstSign>() const {
91     return Integral<DstBits, DstSign>(V);
92   }
93 
94   explicit operator unsigned() const { return V; }
95   explicit operator int64_t() const { return V; }
96   explicit operator uint64_t() const { return V; }
97 
98   APSInt toAPSInt() const {
99     return APSInt(APInt(Bits, static_cast<uint64_t>(V), Signed), !Signed);
100   }
101   APSInt toAPSInt(unsigned NumBits) const {
102     if constexpr (Signed)
103       return APSInt(toAPSInt().sextOrTrunc(NumBits), !Signed);
104     else
105       return APSInt(toAPSInt().zextOrTrunc(NumBits), !Signed);
106   }
107   APValue toAPValue() const { return APValue(toAPSInt()); }
108 
109   Integral<Bits, false> toUnsigned() const {
110     return Integral<Bits, false>(*this);
111   }
112 
113   constexpr static unsigned bitWidth() { return Bits; }
114 
115   bool isZero() const { return !V; }
116 
117   bool isMin() const { return *this == min(bitWidth()); }
118 
119   bool isMinusOne() const { return Signed && V == ReprT(-1); }
120 
121   constexpr static bool isSigned() { return Signed; }
122 
123   bool isNegative() const { return V < ReprT(0); }
124   bool isPositive() const { return !isNegative(); }
125 
126   ComparisonCategoryResult compare(const Integral &RHS) const {
127     return Compare(V, RHS.V);
128   }
129 
130   unsigned countLeadingZeros() const {
131     if constexpr (!Signed)
132       return llvm::countl_zero<ReprT>(V);
133     llvm_unreachable("Don't call countLeadingZeros() on signed types.");
134   }
135 
136   Integral truncate(unsigned TruncBits) const {
137     if (TruncBits >= Bits)
138       return *this;
139     const ReprT BitMask = (ReprT(1) << ReprT(TruncBits)) - 1;
140     const ReprT SignBit = ReprT(1) << (TruncBits - 1);
141     const ReprT ExtMask = ~BitMask;
142     return Integral((V & BitMask) | (Signed && (V & SignBit) ? ExtMask : 0));
143   }
144 
145   void print(llvm::raw_ostream &OS) const { OS << V; }
146 
147   static Integral min(unsigned NumBits) {
148     return Integral(Min);
149   }
150   static Integral max(unsigned NumBits) {
151     return Integral(Max);
152   }
153 
154   template <typename ValT> static Integral from(ValT Value) {
155     if constexpr (std::is_integral<ValT>::value)
156       return Integral(Value);
157     else
158       return Integral::from(static_cast<Integral::ReprT>(Value));
159   }
160 
161   template <unsigned SrcBits, bool SrcSign>
162   static std::enable_if_t<SrcBits != 0, Integral>
163   from(Integral<SrcBits, SrcSign> Value) {
164     return Integral(Value.V);
165   }
166 
167   template <bool SrcSign> static Integral from(Integral<0, SrcSign> Value) {
168     if constexpr (SrcSign)
169       return Integral(Value.V.getSExtValue());
170     else
171       return Integral(Value.V.getZExtValue());
172   }
173 
174   static Integral zero() { return from(0); }
175 
176   template <typename T> static Integral from(T Value, unsigned NumBits) {
177     return Integral(Value);
178   }
179 
180   static bool inRange(int64_t Value, unsigned NumBits) {
181     return CheckRange<ReprT, Min, Max>(Value);
182   }
183 
184   static bool increment(Integral A, Integral *R) {
185     return add(A, Integral(ReprT(1)), A.bitWidth(), R);
186   }
187 
188   static bool decrement(Integral A, Integral *R) {
189     return sub(A, Integral(ReprT(1)), A.bitWidth(), R);
190   }
191 
192   static bool add(Integral A, Integral B, unsigned OpBits, Integral *R) {
193     return CheckAddUB(A.V, B.V, R->V);
194   }
195 
196   static bool sub(Integral A, Integral B, unsigned OpBits, Integral *R) {
197     return CheckSubUB(A.V, B.V, R->V);
198   }
199 
200   static bool mul(Integral A, Integral B, unsigned OpBits, Integral *R) {
201     return CheckMulUB(A.V, B.V, R->V);
202   }
203 
204   static bool rem(Integral A, Integral B, unsigned OpBits, Integral *R) {
205     *R = Integral(A.V % B.V);
206     return false;
207   }
208 
209   static bool div(Integral A, Integral B, unsigned OpBits, Integral *R) {
210     *R = Integral(A.V / B.V);
211     return false;
212   }
213 
214   static bool bitAnd(Integral A, Integral B, unsigned OpBits, Integral *R) {
215     *R = Integral(A.V & B.V);
216     return false;
217   }
218 
219   static bool bitOr(Integral A, Integral B, unsigned OpBits, Integral *R) {
220     *R = Integral(A.V | B.V);
221     return false;
222   }
223 
224   static bool bitXor(Integral A, Integral B, unsigned OpBits, Integral *R) {
225     *R = Integral(A.V ^ B.V);
226     return false;
227   }
228 
229   static bool neg(Integral A, Integral *R) {
230     if (Signed && A.isMin())
231       return true;
232 
233     *R = -A;
234     return false;
235   }
236 
237   static bool comp(Integral A, Integral *R) {
238     *R = Integral(~A.V);
239     return false;
240   }
241 
242   template <unsigned RHSBits, bool RHSSign>
243   static void shiftLeft(const Integral A, const Integral<RHSBits, RHSSign> B,
244                         unsigned OpBits, Integral *R) {
245     *R = Integral::from(A.V << B.V, OpBits);
246   }
247 
248   template <unsigned RHSBits, bool RHSSign>
249   static void shiftRight(const Integral A, const Integral<RHSBits, RHSSign> B,
250                          unsigned OpBits, Integral *R) {
251     *R = Integral::from(A.V >> B.V, OpBits);
252   }
253 
254 private:
255   template <typename T> static bool CheckAddUB(T A, T B, T &R) {
256     if constexpr (std::is_signed_v<T>) {
257       return llvm::AddOverflow<T>(A, B, R);
258     } else {
259       R = A + B;
260       return false;
261     }
262   }
263 
264   template <typename T> static bool CheckSubUB(T A, T B, T &R) {
265     if constexpr (std::is_signed_v<T>) {
266       return llvm::SubOverflow<T>(A, B, R);
267     } else {
268       R = A - B;
269       return false;
270     }
271   }
272 
273   template <typename T> static bool CheckMulUB(T A, T B, T &R) {
274     if constexpr (std::is_signed_v<T>) {
275       return llvm::MulOverflow<T>(A, B, R);
276     } else {
277       R = A * B;
278       return false;
279     }
280   }
281   template <typename T, T Min, T Max> static bool CheckRange(int64_t V) {
282     if constexpr (std::is_signed_v<T>) {
283       return Min <= V && V <= Max;
284     } else {
285       return V >= 0 && static_cast<uint64_t>(V) <= Max;
286     }
287   }
288 };
289 
290 template <unsigned Bits, bool Signed>
291 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, Integral<Bits, Signed> I) {
292   I.print(OS);
293   return OS;
294 }
295 
296 } // namespace interp
297 } // namespace clang
298 
299 #endif
300