1 //== llvm/CodeGen/LowLevelType.h ------------------------------- -*- 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 /// \file
9 /// Implement a low-level type suitable for MachineInstr level instruction
10 /// selection.
11 ///
12 /// For a type attached to a MachineInstr, we only care about 2 details: total
13 /// size and the number of vector lanes (if any). Accordingly, there are 4
14 /// possible valid type-kinds:
15 ///
16 ///    * `sN` for scalars and aggregates
17 ///    * `<N x sM>` for vectors, which must have at least 2 elements.
18 ///    * `pN` for pointers
19 ///
20 /// Other information required for correct selection is expected to be carried
21 /// by the opcode, or non-type flags. For example the distinction between G_ADD
22 /// and G_FADD for int/float or fast-math flags.
23 ///
24 //===----------------------------------------------------------------------===//
25 
26 #ifndef LLVM_CODEGEN_LOWLEVELTYPE_H
27 #define LLVM_CODEGEN_LOWLEVELTYPE_H
28 
29 #include "llvm/ADT/DenseMapInfo.h"
30 #include "llvm/CodeGen/MachineValueType.h"
31 #include "llvm/Support/Debug.h"
32 #include <cassert>
33 
34 namespace llvm {
35 
36 class Type;
37 class raw_ostream;
38 
39 class LLT {
40 public:
41   /// Get a low-level scalar or aggregate "bag of bits".
42   static constexpr LLT scalar(unsigned SizeInBits) {
43     return LLT{/*isPointer=*/false, /*isVector=*/false, /*isScalar=*/true,
44                ElementCount::getFixed(0), SizeInBits,
45                /*AddressSpace=*/0};
46   }
47 
48   /// Get a low-level pointer in the given address space.
49   static constexpr LLT pointer(unsigned AddressSpace, unsigned SizeInBits) {
50     assert(SizeInBits > 0 && "invalid pointer size");
51     return LLT{/*isPointer=*/true, /*isVector=*/false, /*isScalar=*/false,
52                ElementCount::getFixed(0), SizeInBits, AddressSpace};
53   }
54 
55   /// Get a low-level vector of some number of elements and element width.
56   static constexpr LLT vector(ElementCount EC, unsigned ScalarSizeInBits) {
57     assert(!EC.isScalar() && "invalid number of vector elements");
58     return LLT{/*isPointer=*/false, /*isVector=*/true, /*isScalar=*/false,
59                EC, ScalarSizeInBits, /*AddressSpace=*/0};
60   }
61 
62   /// Get a low-level vector of some number of elements and element type.
63   static constexpr LLT vector(ElementCount EC, LLT ScalarTy) {
64     assert(!EC.isScalar() && "invalid number of vector elements");
65     assert(!ScalarTy.isVector() && "invalid vector element type");
66     return LLT{ScalarTy.isPointer(),
67                /*isVector=*/true,
68                /*isScalar=*/false,
69                EC,
70                ScalarTy.getSizeInBits().getFixedValue(),
71                ScalarTy.isPointer() ? ScalarTy.getAddressSpace() : 0};
72   }
73 
74   /// Get a low-level fixed-width vector of some number of elements and element
75   /// width.
76   static constexpr LLT fixed_vector(unsigned NumElements,
77                                     unsigned ScalarSizeInBits) {
78     return vector(ElementCount::getFixed(NumElements), ScalarSizeInBits);
79   }
80 
81   /// Get a low-level fixed-width vector of some number of elements and element
82   /// type.
83   static constexpr LLT fixed_vector(unsigned NumElements, LLT ScalarTy) {
84     return vector(ElementCount::getFixed(NumElements), ScalarTy);
85   }
86 
87   /// Get a low-level scalable vector of some number of elements and element
88   /// width.
89   static constexpr LLT scalable_vector(unsigned MinNumElements,
90                                        unsigned ScalarSizeInBits) {
91     return vector(ElementCount::getScalable(MinNumElements), ScalarSizeInBits);
92   }
93 
94   /// Get a low-level scalable vector of some number of elements and element
95   /// type.
96   static constexpr LLT scalable_vector(unsigned MinNumElements, LLT ScalarTy) {
97     return vector(ElementCount::getScalable(MinNumElements), ScalarTy);
98   }
99 
100   static constexpr LLT scalarOrVector(ElementCount EC, LLT ScalarTy) {
101     return EC.isScalar() ? ScalarTy : LLT::vector(EC, ScalarTy);
102   }
103 
104   static constexpr LLT scalarOrVector(ElementCount EC, uint64_t ScalarSize) {
105     assert(ScalarSize <= std::numeric_limits<unsigned>::max() &&
106            "Not enough bits in LLT to represent size");
107     return scalarOrVector(EC, LLT::scalar(static_cast<unsigned>(ScalarSize)));
108   }
109 
110   explicit constexpr LLT(bool isPointer, bool isVector, bool isScalar,
111                          ElementCount EC, uint64_t SizeInBits,
112                          unsigned AddressSpace)
113       : LLT() {
114     init(isPointer, isVector, isScalar, EC, SizeInBits, AddressSpace);
115   }
116   explicit constexpr LLT()
117       : IsScalar(false), IsPointer(false), IsVector(false), RawData(0) {}
118 
119   explicit LLT(MVT VT);
120 
121   constexpr bool isValid() const { return IsScalar || RawData != 0; }
122 
123   constexpr bool isScalar() const { return IsScalar; }
124 
125   constexpr bool isPointer() const {
126     return isValid() && IsPointer && !IsVector;
127   }
128 
129   constexpr bool isVector() const { return isValid() && IsVector; }
130 
131   /// Returns the number of elements in a vector LLT. Must only be called on
132   /// vector types.
133   constexpr uint16_t getNumElements() const {
134     if (isScalable())
135       llvm::reportInvalidSizeRequest(
136           "Possible incorrect use of LLT::getNumElements() for "
137           "scalable vector. Scalable flag may be dropped, use "
138           "LLT::getElementCount() instead");
139     return getElementCount().getKnownMinValue();
140   }
141 
142   /// Returns true if the LLT is a scalable vector. Must only be called on
143   /// vector types.
144   constexpr bool isScalable() const {
145     assert(isVector() && "Expected a vector type");
146     return IsPointer ? getFieldValue(PointerVectorScalableFieldInfo)
147                      : getFieldValue(VectorScalableFieldInfo);
148   }
149 
150   constexpr ElementCount getElementCount() const {
151     assert(IsVector && "cannot get number of elements on scalar/aggregate");
152     return ElementCount::get(IsPointer
153                                  ? getFieldValue(PointerVectorElementsFieldInfo)
154                                  : getFieldValue(VectorElementsFieldInfo),
155                              isScalable());
156   }
157 
158   /// Returns the total size of the type. Must only be called on sized types.
159   constexpr TypeSize getSizeInBits() const {
160     if (isPointer() || isScalar())
161       return TypeSize::Fixed(getScalarSizeInBits());
162     auto EC = getElementCount();
163     return TypeSize(getScalarSizeInBits() * EC.getKnownMinValue(),
164                     EC.isScalable());
165   }
166 
167   /// Returns the total size of the type in bytes, i.e. number of whole bytes
168   /// needed to represent the size in bits. Must only be called on sized types.
169   constexpr TypeSize getSizeInBytes() const {
170     TypeSize BaseSize = getSizeInBits();
171     return {(BaseSize.getKnownMinValue() + 7) / 8, BaseSize.isScalable()};
172   }
173 
174   constexpr LLT getScalarType() const {
175     return isVector() ? getElementType() : *this;
176   }
177 
178   /// If this type is a vector, return a vector with the same number of elements
179   /// but the new element type. Otherwise, return the new element type.
180   constexpr LLT changeElementType(LLT NewEltTy) const {
181     return isVector() ? LLT::vector(getElementCount(), NewEltTy) : NewEltTy;
182   }
183 
184   /// If this type is a vector, return a vector with the same number of elements
185   /// but the new element size. Otherwise, return the new element type. Invalid
186   /// for pointer types. For pointer types, use changeElementType.
187   constexpr LLT changeElementSize(unsigned NewEltSize) const {
188     assert(!getScalarType().isPointer() &&
189            "invalid to directly change element size for pointers");
190     return isVector() ? LLT::vector(getElementCount(), NewEltSize)
191                       : LLT::scalar(NewEltSize);
192   }
193 
194   /// Return a vector or scalar with the same element type and the new element
195   /// count.
196   constexpr LLT changeElementCount(ElementCount EC) const {
197     return LLT::scalarOrVector(EC, getScalarType());
198   }
199 
200   /// Return a type that is \p Factor times smaller. Reduces the number of
201   /// elements if this is a vector, or the bitwidth for scalar/pointers. Does
202   /// not attempt to handle cases that aren't evenly divisible.
203   constexpr LLT divide(int Factor) const {
204     assert(Factor != 1);
205     assert((!isScalar() || getScalarSizeInBits() != 0) &&
206            "cannot divide scalar of size zero");
207     if (isVector()) {
208       assert(getElementCount().isKnownMultipleOf(Factor));
209       return scalarOrVector(getElementCount().divideCoefficientBy(Factor),
210                             getElementType());
211     }
212 
213     assert(getScalarSizeInBits() % Factor == 0);
214     return scalar(getScalarSizeInBits() / Factor);
215   }
216 
217   /// Produce a vector type that is \p Factor times bigger, preserving the
218   /// element type. For a scalar or pointer, this will produce a new vector with
219   /// \p Factor elements.
220   constexpr LLT multiplyElements(int Factor) const {
221     if (isVector()) {
222       return scalarOrVector(getElementCount().multiplyCoefficientBy(Factor),
223                             getElementType());
224     }
225 
226     return fixed_vector(Factor, *this);
227   }
228 
229   constexpr bool isByteSized() const {
230     return getSizeInBits().isKnownMultipleOf(8);
231   }
232 
233   constexpr unsigned getScalarSizeInBits() const {
234     if (IsScalar)
235       return getFieldValue(ScalarSizeFieldInfo);
236     if (IsVector) {
237       if (!IsPointer)
238         return getFieldValue(VectorSizeFieldInfo);
239       else
240         return getFieldValue(PointerVectorSizeFieldInfo);
241     }
242     assert(IsPointer && "unexpected LLT");
243     return getFieldValue(PointerSizeFieldInfo);
244   }
245 
246   constexpr unsigned getAddressSpace() const {
247     assert(RawData != 0 && "Invalid Type");
248     assert(IsPointer && "cannot get address space of non-pointer type");
249     if (!IsVector)
250       return getFieldValue(PointerAddressSpaceFieldInfo);
251     else
252       return getFieldValue(PointerVectorAddressSpaceFieldInfo);
253   }
254 
255   /// Returns the vector's element type. Only valid for vector types.
256   constexpr LLT getElementType() const {
257     assert(isVector() && "cannot get element type of scalar/aggregate");
258     if (IsPointer)
259       return pointer(getAddressSpace(), getScalarSizeInBits());
260     else
261       return scalar(getScalarSizeInBits());
262   }
263 
264   void print(raw_ostream &OS) const;
265 
266 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
267   LLVM_DUMP_METHOD void dump() const;
268 #endif
269 
270   constexpr bool operator==(const LLT &RHS) const {
271     return IsPointer == RHS.IsPointer && IsVector == RHS.IsVector &&
272            IsScalar == RHS.IsScalar && RHS.RawData == RawData;
273   }
274 
275   constexpr bool operator!=(const LLT &RHS) const { return !(*this == RHS); }
276 
277   friend struct DenseMapInfo<LLT>;
278   friend class GISelInstProfileBuilder;
279 
280 private:
281   /// LLT is packed into 64 bits as follows:
282   /// isScalar : 1
283   /// isPointer : 1
284   /// isVector  : 1
285   /// with 61 bits remaining for Kind-specific data, packed in bitfields
286   /// as described below. As there isn't a simple portable way to pack bits
287   /// into bitfields, here the different fields in the packed structure is
288   /// described in static const *Field variables. Each of these variables
289   /// is a 2-element array, with the first element describing the bitfield size
290   /// and the second element describing the bitfield offset.
291   typedef int BitFieldInfo[2];
292   ///
293   /// This is how the bitfields are packed per Kind:
294   /// * Invalid:
295   ///   gets encoded as RawData == 0, as that is an invalid encoding, since for
296   ///   valid encodings, SizeInBits/SizeOfElement must be larger than 0.
297   /// * Non-pointer scalar (isPointer == 0 && isVector == 0):
298   ///   SizeInBits: 32;
299   static const constexpr BitFieldInfo ScalarSizeFieldInfo{32, 0};
300   /// * Pointer (isPointer == 1 && isVector == 0):
301   ///   SizeInBits: 16;
302   ///   AddressSpace: 24;
303   static const constexpr BitFieldInfo PointerSizeFieldInfo{16, 0};
304   static const constexpr BitFieldInfo PointerAddressSpaceFieldInfo{
305       24, PointerSizeFieldInfo[0] + PointerSizeFieldInfo[1]};
306   static_assert((PointerAddressSpaceFieldInfo[0] +
307                  PointerAddressSpaceFieldInfo[1]) <= 61,
308                 "Insufficient bits to encode all data");
309   /// * Vector-of-non-pointer (isPointer == 0 && isVector == 1):
310   ///   NumElements: 16;
311   ///   SizeOfElement: 32;
312   ///   Scalable: 1;
313   static const constexpr BitFieldInfo VectorElementsFieldInfo{16, 0};
314   static const constexpr BitFieldInfo VectorSizeFieldInfo{
315       32, VectorElementsFieldInfo[0] + VectorElementsFieldInfo[1]};
316   static const constexpr BitFieldInfo VectorScalableFieldInfo{
317       1, VectorSizeFieldInfo[0] + VectorSizeFieldInfo[1]};
318   static_assert((VectorSizeFieldInfo[0] + VectorSizeFieldInfo[1]) <= 61,
319                 "Insufficient bits to encode all data");
320   /// * Vector-of-pointer (isPointer == 1 && isVector == 1):
321   ///   NumElements: 16;
322   ///   SizeOfElement: 16;
323   ///   AddressSpace: 24;
324   ///   Scalable: 1;
325   static const constexpr BitFieldInfo PointerVectorElementsFieldInfo{16, 0};
326   static const constexpr BitFieldInfo PointerVectorSizeFieldInfo{
327       16,
328       PointerVectorElementsFieldInfo[1] + PointerVectorElementsFieldInfo[0]};
329   static const constexpr BitFieldInfo PointerVectorAddressSpaceFieldInfo{
330       24, PointerVectorSizeFieldInfo[1] + PointerVectorSizeFieldInfo[0]};
331   static const constexpr BitFieldInfo PointerVectorScalableFieldInfo{
332       1, PointerVectorAddressSpaceFieldInfo[0] +
333              PointerVectorAddressSpaceFieldInfo[1]};
334   static_assert((PointerVectorAddressSpaceFieldInfo[0] +
335                  PointerVectorAddressSpaceFieldInfo[1]) <= 61,
336                 "Insufficient bits to encode all data");
337 
338   uint64_t IsScalar : 1;
339   uint64_t IsPointer : 1;
340   uint64_t IsVector : 1;
341   uint64_t RawData : 61;
342 
343   static constexpr uint64_t getMask(const BitFieldInfo FieldInfo) {
344     const int FieldSizeInBits = FieldInfo[0];
345     return (((uint64_t)1) << FieldSizeInBits) - 1;
346   }
347   static constexpr uint64_t maskAndShift(uint64_t Val, uint64_t Mask,
348                                          uint8_t Shift) {
349     assert(Val <= Mask && "Value too large for field");
350     return (Val & Mask) << Shift;
351   }
352   static constexpr uint64_t maskAndShift(uint64_t Val,
353                                          const BitFieldInfo FieldInfo) {
354     return maskAndShift(Val, getMask(FieldInfo), FieldInfo[1]);
355   }
356 
357   constexpr uint64_t getFieldValue(const BitFieldInfo FieldInfo) const {
358     return getMask(FieldInfo) & (RawData >> FieldInfo[1]);
359   }
360 
361   constexpr void init(bool IsPointer, bool IsVector, bool IsScalar,
362                       ElementCount EC, uint64_t SizeInBits,
363                       unsigned AddressSpace) {
364     assert(SizeInBits <= std::numeric_limits<unsigned>::max() &&
365            "Not enough bits in LLT to represent size");
366     this->IsPointer = IsPointer;
367     this->IsVector = IsVector;
368     this->IsScalar = IsScalar;
369     if (IsScalar)
370       RawData = maskAndShift(SizeInBits, ScalarSizeFieldInfo);
371     else if (IsVector) {
372       assert(EC.isVector() && "invalid number of vector elements");
373       if (!IsPointer)
374         RawData =
375             maskAndShift(EC.getKnownMinValue(), VectorElementsFieldInfo) |
376             maskAndShift(SizeInBits, VectorSizeFieldInfo) |
377             maskAndShift(EC.isScalable() ? 1 : 0, VectorScalableFieldInfo);
378       else
379         RawData =
380             maskAndShift(EC.getKnownMinValue(),
381                          PointerVectorElementsFieldInfo) |
382             maskAndShift(SizeInBits, PointerVectorSizeFieldInfo) |
383             maskAndShift(AddressSpace, PointerVectorAddressSpaceFieldInfo) |
384             maskAndShift(EC.isScalable() ? 1 : 0,
385                          PointerVectorScalableFieldInfo);
386     } else if (IsPointer)
387       RawData = maskAndShift(SizeInBits, PointerSizeFieldInfo) |
388                 maskAndShift(AddressSpace, PointerAddressSpaceFieldInfo);
389     else
390       llvm_unreachable("unexpected LLT configuration");
391   }
392 
393 public:
394   constexpr uint64_t getUniqueRAWLLTData() const {
395     return ((uint64_t)RawData) << 3 | ((uint64_t)IsScalar) << 2 |
396            ((uint64_t)IsPointer) << 1 | ((uint64_t)IsVector);
397   }
398 };
399 
400 inline raw_ostream& operator<<(raw_ostream &OS, const LLT &Ty) {
401   Ty.print(OS);
402   return OS;
403 }
404 
405 template<> struct DenseMapInfo<LLT> {
406   static inline LLT getEmptyKey() {
407     LLT Invalid;
408     Invalid.IsPointer = true;
409     return Invalid;
410   }
411   static inline LLT getTombstoneKey() {
412     LLT Invalid;
413     Invalid.IsVector = true;
414     return Invalid;
415   }
416   static inline unsigned getHashValue(const LLT &Ty) {
417     uint64_t Val = Ty.getUniqueRAWLLTData();
418     return DenseMapInfo<uint64_t>::getHashValue(Val);
419   }
420   static bool isEqual(const LLT &LHS, const LLT &RHS) {
421     return LHS == RHS;
422   }
423 };
424 
425 }
426 
427 #endif // LLVM_CODEGEN_LOWLEVELTYPE_H
428