1 //===- RDFRegisters.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 
9 #ifndef LLVM_CODEGEN_RDFREGISTERS_H
10 #define LLVM_CODEGEN_RDFREGISTERS_H
11 
12 #include "llvm/ADT/BitVector.h"
13 #include "llvm/ADT/STLExtras.h"
14 #include "llvm/ADT/iterator_range.h"
15 #include "llvm/CodeGen/TargetRegisterInfo.h"
16 #include "llvm/MC/LaneBitmask.h"
17 #include "llvm/MC/MCRegister.h"
18 #include <cassert>
19 #include <cstdint>
20 #include <map>
21 #include <set>
22 #include <vector>
23 
24 namespace llvm {
25 
26 class MachineFunction;
27 class raw_ostream;
28 
29 namespace rdf {
30 struct RegisterAggr;
31 
32 using RegisterId = uint32_t;
33 
34 template <typename T>
35 bool disjoint(const std::set<T> &A, const std::set<T> &B) {
36   auto ItA = A.begin(), EndA = A.end();
37   auto ItB = B.begin(), EndB = B.end();
38   while (ItA != EndA && ItB != EndB) {
39     if (*ItA < *ItB)
40       ++ItA;
41     else if (*ItB < *ItA)
42       ++ItB;
43     else
44       return false;
45   }
46   return true;
47 }
48 
49 // Template class for a map translating uint32_t into arbitrary types.
50 // The map will act like an indexed set: upon insertion of a new object,
51 // it will automatically assign a new index to it. Index of 0 is treated
52 // as invalid and is never allocated.
53 template <typename T, unsigned N = 32> struct IndexedSet {
54   IndexedSet() { Map.reserve(N); }
55 
56   T get(uint32_t Idx) const {
57     // Index Idx corresponds to Map[Idx-1].
58     assert(Idx != 0 && !Map.empty() && Idx - 1 < Map.size());
59     return Map[Idx - 1];
60   }
61 
62   uint32_t insert(T Val) {
63     // Linear search.
64     auto F = llvm::find(Map, Val);
65     if (F != Map.end())
66       return F - Map.begin() + 1;
67     Map.push_back(Val);
68     return Map.size(); // Return actual_index + 1.
69   }
70 
71   uint32_t find(T Val) const {
72     auto F = llvm::find(Map, Val);
73     assert(F != Map.end());
74     return F - Map.begin() + 1;
75   }
76 
77   uint32_t size() const { return Map.size(); }
78 
79   using const_iterator = typename std::vector<T>::const_iterator;
80 
81   const_iterator begin() const { return Map.begin(); }
82   const_iterator end() const { return Map.end(); }
83 
84 private:
85   std::vector<T> Map;
86 };
87 
88 struct RegisterRef {
89   RegisterId Reg = 0;
90   LaneBitmask Mask = LaneBitmask::getNone(); // Only for registers.
91 
92   constexpr RegisterRef() = default;
93   constexpr explicit RegisterRef(RegisterId R,
94                                  LaneBitmask M = LaneBitmask::getAll())
95       : Reg(R), Mask(isRegId(R) && R != 0 ? M : LaneBitmask::getNone()) {}
96 
97   // Classify null register as a "register".
98   constexpr bool isReg() const { return Reg == 0 || isRegId(Reg); }
99   constexpr bool isUnit() const { return isUnitId(Reg); }
100   constexpr bool isMask() const { return isMaskId(Reg); }
101 
102   constexpr unsigned idx() const { return toIdx(Reg); }
103 
104   constexpr operator bool() const {
105     return !isReg() || (Reg != 0 && Mask.any());
106   }
107 
108   size_t hash() const {
109     return std::hash<RegisterId>{}(Reg) ^
110            std::hash<LaneBitmask::Type>{}(Mask.getAsInteger());
111   }
112 
113   static constexpr bool isRegId(unsigned Id) {
114     return Register::isPhysicalRegister(Id);
115   }
116   static constexpr bool isUnitId(unsigned Id) {
117     return Register::isVirtualRegister(Id);
118   }
119   static constexpr bool isMaskId(unsigned Id) {
120     return Register::isStackSlot(Id);
121   }
122 
123   static constexpr RegisterId toUnitId(unsigned Idx) {
124     return Idx | MCRegister::VirtualRegFlag;
125   }
126 
127   static constexpr unsigned toIdx(RegisterId Id) {
128     // Not using virtReg2Index or stackSlot2Index, because they are
129     // not constexpr.
130     if (isUnitId(Id))
131       return Id & ~MCRegister::VirtualRegFlag;
132     // RegId and MaskId are unchanged.
133     return Id;
134   }
135 
136   bool operator<(RegisterRef) const = delete;
137   bool operator==(RegisterRef) const = delete;
138   bool operator!=(RegisterRef) const = delete;
139 };
140 
141 struct PhysicalRegisterInfo {
142   PhysicalRegisterInfo(const TargetRegisterInfo &tri,
143                        const MachineFunction &mf);
144 
145   RegisterId getRegMaskId(const uint32_t *RM) const {
146     return Register::index2StackSlot(RegMasks.find(RM));
147   }
148 
149   const uint32_t *getRegMaskBits(RegisterId R) const {
150     return RegMasks.get(Register::stackSlot2Index(R));
151   }
152 
153   bool alias(RegisterRef RA, RegisterRef RB) const;
154 
155   // Returns the set of aliased physical registers.
156   std::set<RegisterId> getAliasSet(RegisterId Reg) const;
157 
158   RegisterRef getRefForUnit(uint32_t U) const {
159     return RegisterRef(UnitInfos[U].Reg, UnitInfos[U].Mask);
160   }
161 
162   const BitVector &getMaskUnits(RegisterId MaskId) const {
163     return MaskInfos[Register::stackSlot2Index(MaskId)].Units;
164   }
165 
166   std::set<RegisterId> getUnits(RegisterRef RR) const;
167 
168   const BitVector &getUnitAliases(uint32_t U) const {
169     return AliasInfos[U].Regs;
170   }
171 
172   RegisterRef mapTo(RegisterRef RR, unsigned R) const;
173   const TargetRegisterInfo &getTRI() const { return TRI; }
174 
175   bool equal_to(RegisterRef A, RegisterRef B) const;
176   bool less(RegisterRef A, RegisterRef B) const;
177 
178   void print(raw_ostream &OS, RegisterRef A) const;
179   void print(raw_ostream &OS, const RegisterAggr &A) const;
180 
181 private:
182   struct RegInfo {
183     const TargetRegisterClass *RegClass = nullptr;
184   };
185   struct UnitInfo {
186     RegisterId Reg = 0;
187     LaneBitmask Mask;
188   };
189   struct MaskInfo {
190     BitVector Units;
191   };
192   struct AliasInfo {
193     BitVector Regs;
194   };
195 
196   const TargetRegisterInfo &TRI;
197   IndexedSet<const uint32_t *> RegMasks;
198   std::vector<RegInfo> RegInfos;
199   std::vector<UnitInfo> UnitInfos;
200   std::vector<MaskInfo> MaskInfos;
201   std::vector<AliasInfo> AliasInfos;
202 };
203 
204 struct RegisterAggr {
205   RegisterAggr(const PhysicalRegisterInfo &pri)
206       : Units(pri.getTRI().getNumRegUnits()), PRI(pri) {}
207   RegisterAggr(const RegisterAggr &RG) = default;
208 
209   unsigned size() const { return Units.count(); }
210   bool empty() const { return Units.none(); }
211   bool hasAliasOf(RegisterRef RR) const;
212   bool hasCoverOf(RegisterRef RR) const;
213 
214   const PhysicalRegisterInfo &getPRI() const { return PRI; }
215 
216   bool operator==(const RegisterAggr &A) const {
217     return DenseMapInfo<BitVector>::isEqual(Units, A.Units);
218   }
219 
220   static bool isCoverOf(RegisterRef RA, RegisterRef RB,
221                         const PhysicalRegisterInfo &PRI) {
222     return RegisterAggr(PRI).insert(RA).hasCoverOf(RB);
223   }
224 
225   RegisterAggr &insert(RegisterRef RR);
226   RegisterAggr &insert(const RegisterAggr &RG);
227   RegisterAggr &intersect(RegisterRef RR);
228   RegisterAggr &intersect(const RegisterAggr &RG);
229   RegisterAggr &clear(RegisterRef RR);
230   RegisterAggr &clear(const RegisterAggr &RG);
231 
232   RegisterRef intersectWith(RegisterRef RR) const;
233   RegisterRef clearIn(RegisterRef RR) const;
234   RegisterRef makeRegRef() const;
235 
236   size_t hash() const { return DenseMapInfo<BitVector>::getHashValue(Units); }
237 
238   struct ref_iterator {
239     using MapType = std::map<RegisterId, LaneBitmask>;
240 
241   private:
242     MapType Masks;
243     MapType::iterator Pos;
244     unsigned Index;
245     const RegisterAggr *Owner;
246 
247   public:
248     ref_iterator(const RegisterAggr &RG, bool End);
249 
250     RegisterRef operator*() const {
251       return RegisterRef(Pos->first, Pos->second);
252     }
253 
254     ref_iterator &operator++() {
255       ++Pos;
256       ++Index;
257       return *this;
258     }
259 
260     bool operator==(const ref_iterator &I) const {
261       assert(Owner == I.Owner);
262       (void)Owner;
263       return Index == I.Index;
264     }
265 
266     bool operator!=(const ref_iterator &I) const { return !(*this == I); }
267   };
268 
269   ref_iterator ref_begin() const { return ref_iterator(*this, false); }
270   ref_iterator ref_end() const { return ref_iterator(*this, true); }
271 
272   using unit_iterator = typename BitVector::const_set_bits_iterator;
273   unit_iterator unit_begin() const { return Units.set_bits_begin(); }
274   unit_iterator unit_end() const { return Units.set_bits_end(); }
275 
276   iterator_range<ref_iterator> refs() const {
277     return make_range(ref_begin(), ref_end());
278   }
279   iterator_range<unit_iterator> units() const {
280     return make_range(unit_begin(), unit_end());
281   }
282 
283 private:
284   BitVector Units;
285   const PhysicalRegisterInfo &PRI;
286 };
287 
288 // This is really a std::map, except that it provides a non-trivial
289 // default constructor to the element accessed via [].
290 template <typename KeyType> struct RegisterAggrMap {
291   RegisterAggrMap(const PhysicalRegisterInfo &pri) : Empty(pri) {}
292 
293   RegisterAggr &operator[](KeyType Key) {
294     return Map.emplace(Key, Empty).first->second;
295   }
296 
297   auto begin() { return Map.begin(); }
298   auto end() { return Map.end(); }
299   auto begin() const { return Map.begin(); }
300   auto end() const { return Map.end(); }
301   auto find(const KeyType &Key) const { return Map.find(Key); }
302 
303 private:
304   RegisterAggr Empty;
305   std::map<KeyType, RegisterAggr> Map;
306 
307 public:
308   using key_type = typename decltype(Map)::key_type;
309   using mapped_type = typename decltype(Map)::mapped_type;
310   using value_type = typename decltype(Map)::value_type;
311 };
312 
313 raw_ostream &operator<<(raw_ostream &OS, const RegisterAggr &A);
314 
315 // Print the lane mask in a short form (or not at all if all bits are set).
316 struct PrintLaneMaskShort {
317   PrintLaneMaskShort(LaneBitmask M) : Mask(M) {}
318   LaneBitmask Mask;
319 };
320 raw_ostream &operator<<(raw_ostream &OS, const PrintLaneMaskShort &P);
321 
322 } // end namespace rdf
323 } // end namespace llvm
324 
325 namespace std {
326 
327 template <> struct hash<llvm::rdf::RegisterRef> {
328   size_t operator()(llvm::rdf::RegisterRef A) const { //
329     return A.hash();
330   }
331 };
332 
333 template <> struct hash<llvm::rdf::RegisterAggr> {
334   size_t operator()(const llvm::rdf::RegisterAggr &A) const { //
335     return A.hash();
336   }
337 };
338 
339 template <> struct equal_to<llvm::rdf::RegisterRef> {
340   constexpr equal_to(const llvm::rdf::PhysicalRegisterInfo &pri) : PRI(&pri) {}
341 
342   bool operator()(llvm::rdf::RegisterRef A, llvm::rdf::RegisterRef B) const {
343     return PRI->equal_to(A, B);
344   }
345 
346 private:
347   // Make it a pointer just in case. See comment in `less` below.
348   const llvm::rdf::PhysicalRegisterInfo *PRI;
349 };
350 
351 template <> struct equal_to<llvm::rdf::RegisterAggr> {
352   bool operator()(const llvm::rdf::RegisterAggr &A,
353                   const llvm::rdf::RegisterAggr &B) const {
354     return A == B;
355   }
356 };
357 
358 template <> struct less<llvm::rdf::RegisterRef> {
359   constexpr less(const llvm::rdf::PhysicalRegisterInfo &pri) : PRI(&pri) {}
360 
361   bool operator()(llvm::rdf::RegisterRef A, llvm::rdf::RegisterRef B) const {
362     return PRI->less(A, B);
363   }
364 
365 private:
366   // Make it a pointer because apparently some versions of MSVC use std::swap
367   // on the std::less specialization.
368   const llvm::rdf::PhysicalRegisterInfo *PRI;
369 };
370 
371 } // namespace std
372 
373 namespace llvm::rdf {
374 using RegisterSet = std::set<RegisterRef, std::less<RegisterRef>>;
375 } // namespace llvm::rdf
376 
377 #endif // LLVM_CODEGEN_RDFREGISTERS_H
378