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     } else if (IsPointer)
242       return getFieldValue(PointerSizeFieldInfo);
243     else
244       llvm_unreachable("unexpected LLT");
245   }
246 
247   constexpr unsigned getAddressSpace() const {
248     assert(RawData != 0 && "Invalid Type");
249     assert(IsPointer && "cannot get address space of non-pointer type");
250     if (!IsVector)
251       return getFieldValue(PointerAddressSpaceFieldInfo);
252     else
253       return getFieldValue(PointerVectorAddressSpaceFieldInfo);
254   }
255 
256   /// Returns the vector's element type. Only valid for vector types.
257   constexpr LLT getElementType() const {
258     assert(isVector() && "cannot get element type of scalar/aggregate");
259     if (IsPointer)
260       return pointer(getAddressSpace(), getScalarSizeInBits());
261     else
262       return scalar(getScalarSizeInBits());
263   }
264 
265   void print(raw_ostream &OS) const;
266 
267 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
268   LLVM_DUMP_METHOD void dump() const;
269 #endif
270 
271   constexpr bool operator==(const LLT &RHS) const {
272     return IsPointer == RHS.IsPointer && IsVector == RHS.IsVector &&
273            IsScalar == RHS.IsScalar && RHS.RawData == RawData;
274   }
275 
276   constexpr bool operator!=(const LLT &RHS) const { return !(*this == RHS); }
277 
278   friend struct DenseMapInfo<LLT>;
279   friend class GISelInstProfileBuilder;
280 
281 private:
282   /// LLT is packed into 64 bits as follows:
283   /// isScalar : 1
284   /// isPointer : 1
285   /// isVector  : 1
286   /// with 61 bits remaining for Kind-specific data, packed in bitfields
287   /// as described below. As there isn't a simple portable way to pack bits
288   /// into bitfields, here the different fields in the packed structure is
289   /// described in static const *Field variables. Each of these variables
290   /// is a 2-element array, with the first element describing the bitfield size
291   /// and the second element describing the bitfield offset.
292   typedef int BitFieldInfo[2];
293   ///
294   /// This is how the bitfields are packed per Kind:
295   /// * Invalid:
296   ///   gets encoded as RawData == 0, as that is an invalid encoding, since for
297   ///   valid encodings, SizeInBits/SizeOfElement must be larger than 0.
298   /// * Non-pointer scalar (isPointer == 0 && isVector == 0):
299   ///   SizeInBits: 32;
300   static const constexpr BitFieldInfo ScalarSizeFieldInfo{32, 0};
301   /// * Pointer (isPointer == 1 && isVector == 0):
302   ///   SizeInBits: 16;
303   ///   AddressSpace: 24;
304   static const constexpr BitFieldInfo PointerSizeFieldInfo{16, 0};
305   static const constexpr BitFieldInfo PointerAddressSpaceFieldInfo{
306       24, PointerSizeFieldInfo[0] + PointerSizeFieldInfo[1]};
307   static_assert((PointerAddressSpaceFieldInfo[0] +
308                  PointerAddressSpaceFieldInfo[1]) <= 61,
309                 "Insufficient bits to encode all data");
310   /// * Vector-of-non-pointer (isPointer == 0 && isVector == 1):
311   ///   NumElements: 16;
312   ///   SizeOfElement: 32;
313   ///   Scalable: 1;
314   static const constexpr BitFieldInfo VectorElementsFieldInfo{16, 0};
315   static const constexpr BitFieldInfo VectorSizeFieldInfo{
316       32, VectorElementsFieldInfo[0] + VectorElementsFieldInfo[1]};
317   static const constexpr BitFieldInfo VectorScalableFieldInfo{
318       1, VectorSizeFieldInfo[0] + VectorSizeFieldInfo[1]};
319   static_assert((VectorSizeFieldInfo[0] + VectorSizeFieldInfo[1]) <= 61,
320                 "Insufficient bits to encode all data");
321   /// * Vector-of-pointer (isPointer == 1 && isVector == 1):
322   ///   NumElements: 16;
323   ///   SizeOfElement: 16;
324   ///   AddressSpace: 24;
325   ///   Scalable: 1;
326   static const constexpr BitFieldInfo PointerVectorElementsFieldInfo{16, 0};
327   static const constexpr BitFieldInfo PointerVectorSizeFieldInfo{
328       16,
329       PointerVectorElementsFieldInfo[1] + PointerVectorElementsFieldInfo[0]};
330   static const constexpr BitFieldInfo PointerVectorAddressSpaceFieldInfo{
331       24, PointerVectorSizeFieldInfo[1] + PointerVectorSizeFieldInfo[0]};
332   static const constexpr BitFieldInfo PointerVectorScalableFieldInfo{
333       1, PointerVectorAddressSpaceFieldInfo[0] +
334              PointerVectorAddressSpaceFieldInfo[1]};
335   static_assert((PointerVectorAddressSpaceFieldInfo[0] +
336                  PointerVectorAddressSpaceFieldInfo[1]) <= 61,
337                 "Insufficient bits to encode all data");
338 
339   uint64_t IsScalar : 1;
340   uint64_t IsPointer : 1;
341   uint64_t IsVector : 1;
342   uint64_t RawData : 61;
343 
344   static constexpr uint64_t getMask(const BitFieldInfo FieldInfo) {
345     const int FieldSizeInBits = FieldInfo[0];
346     return (((uint64_t)1) << FieldSizeInBits) - 1;
347   }
348   static constexpr uint64_t maskAndShift(uint64_t Val, uint64_t Mask,
349                                          uint8_t Shift) {
350     assert(Val <= Mask && "Value too large for field");
351     return (Val & Mask) << Shift;
352   }
353   static constexpr uint64_t maskAndShift(uint64_t Val,
354                                          const BitFieldInfo FieldInfo) {
355     return maskAndShift(Val, getMask(FieldInfo), FieldInfo[1]);
356   }
357 
358   constexpr uint64_t getFieldValue(const BitFieldInfo FieldInfo) const {
359     return getMask(FieldInfo) & (RawData >> FieldInfo[1]);
360   }
361 
362   constexpr void init(bool IsPointer, bool IsVector, bool IsScalar,
363                       ElementCount EC, uint64_t SizeInBits,
364                       unsigned AddressSpace) {
365     assert(SizeInBits <= std::numeric_limits<unsigned>::max() &&
366            "Not enough bits in LLT to represent size");
367     this->IsPointer = IsPointer;
368     this->IsVector = IsVector;
369     this->IsScalar = IsScalar;
370     if (IsScalar)
371       RawData = maskAndShift(SizeInBits, ScalarSizeFieldInfo);
372     else if (IsVector) {
373       assert(EC.isVector() && "invalid number of vector elements");
374       if (!IsPointer)
375         RawData =
376             maskAndShift(EC.getKnownMinValue(), VectorElementsFieldInfo) |
377             maskAndShift(SizeInBits, VectorSizeFieldInfo) |
378             maskAndShift(EC.isScalable() ? 1 : 0, VectorScalableFieldInfo);
379       else
380         RawData =
381             maskAndShift(EC.getKnownMinValue(),
382                          PointerVectorElementsFieldInfo) |
383             maskAndShift(SizeInBits, PointerVectorSizeFieldInfo) |
384             maskAndShift(AddressSpace, PointerVectorAddressSpaceFieldInfo) |
385             maskAndShift(EC.isScalable() ? 1 : 0,
386                          PointerVectorScalableFieldInfo);
387     } else if (IsPointer)
388       RawData = maskAndShift(SizeInBits, PointerSizeFieldInfo) |
389                 maskAndShift(AddressSpace, PointerAddressSpaceFieldInfo);
390     else
391       llvm_unreachable("unexpected LLT configuration");
392   }
393 
394 public:
395   constexpr uint64_t getUniqueRAWLLTData() const {
396     return ((uint64_t)RawData) << 3 | ((uint64_t)IsScalar) << 2 |
397            ((uint64_t)IsPointer) << 1 | ((uint64_t)IsVector);
398   }
399 };
400 
401 inline raw_ostream& operator<<(raw_ostream &OS, const LLT &Ty) {
402   Ty.print(OS);
403   return OS;
404 }
405 
406 template<> struct DenseMapInfo<LLT> {
407   static inline LLT getEmptyKey() {
408     LLT Invalid;
409     Invalid.IsPointer = true;
410     return Invalid;
411   }
412   static inline LLT getTombstoneKey() {
413     LLT Invalid;
414     Invalid.IsVector = true;
415     return Invalid;
416   }
417   static inline unsigned getHashValue(const LLT &Ty) {
418     uint64_t Val = Ty.getUniqueRAWLLTData();
419     return DenseMapInfo<uint64_t>::getHashValue(Val);
420   }
421   static bool isEqual(const LLT &LHS, const LLT &RHS) {
422     return LHS == RHS;
423   }
424 };
425 
426 }
427 
428 #endif // LLVM_CODEGEN_LOWLEVELTYPE_H
429