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>
disjoint(const std::set<T> & A,const std::set<T> & B)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 {
IndexedSetIndexedSet54 IndexedSet() { Map.reserve(N); }
55
getIndexedSet56 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
insertIndexedSet62 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
findIndexedSet71 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
sizeIndexedSet77 uint32_t size() const { return Map.size(); }
78
79 using const_iterator = typename std::vector<T>::const_iterator;
80
beginIndexedSet81 const_iterator begin() const { return Map.begin(); }
endIndexedSet82 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())
RegRegisterRef95 : Reg(R), Mask(isRegId(R) && R != 0 ? M : LaneBitmask::getNone()) {}
96
97 // Classify null register as a "register".
isRegRegisterRef98 constexpr bool isReg() const { return Reg == 0 || isRegId(Reg); }
isUnitRegisterRef99 constexpr bool isUnit() const { return isUnitId(Reg); }
isMaskRegisterRef100 constexpr bool isMask() const { return isMaskId(Reg); }
101
idxRegisterRef102 constexpr unsigned idx() const { return toIdx(Reg); }
103
104 constexpr operator bool() const {
105 return !isReg() || (Reg != 0 && Mask.any());
106 }
107
hashRegisterRef108 size_t hash() const {
109 return std::hash<RegisterId>{}(Reg) ^
110 std::hash<LaneBitmask::Type>{}(Mask.getAsInteger());
111 }
112
isRegIdRegisterRef113 static constexpr bool isRegId(unsigned Id) {
114 return Register::isPhysicalRegister(Id);
115 }
isUnitIdRegisterRef116 static constexpr bool isUnitId(unsigned Id) {
117 return Register::isVirtualRegister(Id);
118 }
isMaskIdRegisterRef119 static constexpr bool isMaskId(unsigned Id) { return Register(Id).isStack(); }
120
toUnitIdRegisterRef121 static constexpr RegisterId toUnitId(unsigned Idx) {
122 return Idx | Register::VirtualRegFlag;
123 }
124
toIdxRegisterRef125 static constexpr unsigned toIdx(RegisterId Id) {
126 // Not using virtReg2Index or stackSlot2Index, because they are
127 // not constexpr.
128 if (isUnitId(Id))
129 return Id & ~Register::VirtualRegFlag;
130 // RegId and MaskId are unchanged.
131 return Id;
132 }
133
134 bool operator<(RegisterRef) const = delete;
135 bool operator==(RegisterRef) const = delete;
136 bool operator!=(RegisterRef) const = delete;
137 };
138
139 struct PhysicalRegisterInfo {
140 PhysicalRegisterInfo(const TargetRegisterInfo &tri,
141 const MachineFunction &mf);
142
getRegMaskIdPhysicalRegisterInfo143 RegisterId getRegMaskId(const uint32_t *RM) const {
144 return Register::index2StackSlot(RegMasks.find(RM));
145 }
146
getRegMaskBitsPhysicalRegisterInfo147 const uint32_t *getRegMaskBits(RegisterId R) const {
148 return RegMasks.get(Register(R).stackSlotIndex());
149 }
150
151 bool alias(RegisterRef RA, RegisterRef RB) const;
152
153 // Returns the set of aliased physical registers.
154 std::set<RegisterId> getAliasSet(RegisterId Reg) const;
155
getRefForUnitPhysicalRegisterInfo156 RegisterRef getRefForUnit(uint32_t U) const {
157 return RegisterRef(UnitInfos[U].Reg, UnitInfos[U].Mask);
158 }
159
getMaskUnitsPhysicalRegisterInfo160 const BitVector &getMaskUnits(RegisterId MaskId) const {
161 return MaskInfos[Register(MaskId).stackSlotIndex()].Units;
162 }
163
164 std::set<RegisterId> getUnits(RegisterRef RR) const;
165
getUnitAliasesPhysicalRegisterInfo166 const BitVector &getUnitAliases(uint32_t U) const {
167 return AliasInfos[U].Regs;
168 }
169
170 RegisterRef mapTo(RegisterRef RR, unsigned R) const;
getTRIPhysicalRegisterInfo171 const TargetRegisterInfo &getTRI() const { return TRI; }
172
173 bool equal_to(RegisterRef A, RegisterRef B) const;
174 bool less(RegisterRef A, RegisterRef B) const;
175
176 void print(raw_ostream &OS, RegisterRef A) const;
177 void print(raw_ostream &OS, const RegisterAggr &A) const;
178
179 private:
180 struct RegInfo {
181 const TargetRegisterClass *RegClass = nullptr;
182 };
183 struct UnitInfo {
184 RegisterId Reg = 0;
185 LaneBitmask Mask;
186 };
187 struct MaskInfo {
188 BitVector Units;
189 };
190 struct AliasInfo {
191 BitVector Regs;
192 };
193
194 const TargetRegisterInfo &TRI;
195 IndexedSet<const uint32_t *> RegMasks;
196 std::vector<RegInfo> RegInfos;
197 std::vector<UnitInfo> UnitInfos;
198 std::vector<MaskInfo> MaskInfos;
199 std::vector<AliasInfo> AliasInfos;
200 };
201
202 struct RegisterAggr {
RegisterAggrRegisterAggr203 RegisterAggr(const PhysicalRegisterInfo &pri)
204 : Units(pri.getTRI().getNumRegUnits()), PRI(pri) {}
205 RegisterAggr(const RegisterAggr &RG) = default;
206
sizeRegisterAggr207 unsigned size() const { return Units.count(); }
emptyRegisterAggr208 bool empty() const { return Units.none(); }
209 bool hasAliasOf(RegisterRef RR) const;
210 bool hasCoverOf(RegisterRef RR) const;
211
getPRIRegisterAggr212 const PhysicalRegisterInfo &getPRI() const { return PRI; }
213
214 bool operator==(const RegisterAggr &A) const {
215 return DenseMapInfo<BitVector>::isEqual(Units, A.Units);
216 }
217
isCoverOfRegisterAggr218 static bool isCoverOf(RegisterRef RA, RegisterRef RB,
219 const PhysicalRegisterInfo &PRI) {
220 return RegisterAggr(PRI).insert(RA).hasCoverOf(RB);
221 }
222
223 RegisterAggr &insert(RegisterRef RR);
224 RegisterAggr &insert(const RegisterAggr &RG);
225 RegisterAggr &intersect(RegisterRef RR);
226 RegisterAggr &intersect(const RegisterAggr &RG);
227 RegisterAggr &clear(RegisterRef RR);
228 RegisterAggr &clear(const RegisterAggr &RG);
229
230 RegisterRef intersectWith(RegisterRef RR) const;
231 RegisterRef clearIn(RegisterRef RR) const;
232 RegisterRef makeRegRef() const;
233
hashRegisterAggr234 size_t hash() const { return DenseMapInfo<BitVector>::getHashValue(Units); }
235
236 struct ref_iterator {
237 using MapType = std::map<RegisterId, LaneBitmask>;
238
239 private:
240 MapType Masks;
241 MapType::iterator Pos;
242 unsigned Index;
243 const RegisterAggr *Owner;
244
245 public:
246 ref_iterator(const RegisterAggr &RG, bool End);
247
248 RegisterRef operator*() const {
249 return RegisterRef(Pos->first, Pos->second);
250 }
251
252 ref_iterator &operator++() {
253 ++Pos;
254 ++Index;
255 return *this;
256 }
257
258 bool operator==(const ref_iterator &I) const {
259 assert(Owner == I.Owner);
260 (void)Owner;
261 return Index == I.Index;
262 }
263
264 bool operator!=(const ref_iterator &I) const { return !(*this == I); }
265 };
266
ref_beginRegisterAggr267 ref_iterator ref_begin() const { return ref_iterator(*this, false); }
ref_endRegisterAggr268 ref_iterator ref_end() const { return ref_iterator(*this, true); }
269
270 using unit_iterator = typename BitVector::const_set_bits_iterator;
unit_beginRegisterAggr271 unit_iterator unit_begin() const { return Units.set_bits_begin(); }
unit_endRegisterAggr272 unit_iterator unit_end() const { return Units.set_bits_end(); }
273
refsRegisterAggr274 iterator_range<ref_iterator> refs() const {
275 return make_range(ref_begin(), ref_end());
276 }
unitsRegisterAggr277 iterator_range<unit_iterator> units() const {
278 return make_range(unit_begin(), unit_end());
279 }
280
281 private:
282 BitVector Units;
283 const PhysicalRegisterInfo &PRI;
284 };
285
286 // This is really a std::map, except that it provides a non-trivial
287 // default constructor to the element accessed via [].
288 template <typename KeyType> struct RegisterAggrMap {
RegisterAggrMapRegisterAggrMap289 RegisterAggrMap(const PhysicalRegisterInfo &pri) : Empty(pri) {}
290
291 RegisterAggr &operator[](KeyType Key) {
292 return Map.emplace(Key, Empty).first->second;
293 }
294
beginRegisterAggrMap295 auto begin() { return Map.begin(); }
endRegisterAggrMap296 auto end() { return Map.end(); }
beginRegisterAggrMap297 auto begin() const { return Map.begin(); }
endRegisterAggrMap298 auto end() const { return Map.end(); }
findRegisterAggrMap299 auto find(const KeyType &Key) const { return Map.find(Key); }
300
301 private:
302 RegisterAggr Empty;
303 std::map<KeyType, RegisterAggr> Map;
304
305 public:
306 using key_type = typename decltype(Map)::key_type;
307 using mapped_type = typename decltype(Map)::mapped_type;
308 using value_type = typename decltype(Map)::value_type;
309 };
310
311 raw_ostream &operator<<(raw_ostream &OS, const RegisterAggr &A);
312
313 // Print the lane mask in a short form (or not at all if all bits are set).
314 struct PrintLaneMaskShort {
PrintLaneMaskShortPrintLaneMaskShort315 PrintLaneMaskShort(LaneBitmask M) : Mask(M) {}
316 LaneBitmask Mask;
317 };
318 raw_ostream &operator<<(raw_ostream &OS, const PrintLaneMaskShort &P);
319
320 } // end namespace rdf
321 } // end namespace llvm
322
323 namespace std {
324
325 template <> struct hash<llvm::rdf::RegisterRef> {
326 size_t operator()(llvm::rdf::RegisterRef A) const { //
327 return A.hash();
328 }
329 };
330
331 template <> struct hash<llvm::rdf::RegisterAggr> {
332 size_t operator()(const llvm::rdf::RegisterAggr &A) const { //
333 return A.hash();
334 }
335 };
336
337 template <> struct equal_to<llvm::rdf::RegisterRef> {
338 constexpr equal_to(const llvm::rdf::PhysicalRegisterInfo &pri) : PRI(&pri) {}
339
340 bool operator()(llvm::rdf::RegisterRef A, llvm::rdf::RegisterRef B) const {
341 return PRI->equal_to(A, B);
342 }
343
344 private:
345 // Make it a pointer just in case. See comment in `less` below.
346 const llvm::rdf::PhysicalRegisterInfo *PRI;
347 };
348
349 template <> struct equal_to<llvm::rdf::RegisterAggr> {
350 bool operator()(const llvm::rdf::RegisterAggr &A,
351 const llvm::rdf::RegisterAggr &B) const {
352 return A == B;
353 }
354 };
355
356 template <> struct less<llvm::rdf::RegisterRef> {
357 constexpr less(const llvm::rdf::PhysicalRegisterInfo &pri) : PRI(&pri) {}
358
359 bool operator()(llvm::rdf::RegisterRef A, llvm::rdf::RegisterRef B) const {
360 return PRI->less(A, B);
361 }
362
363 private:
364 // Make it a pointer because apparently some versions of MSVC use std::swap
365 // on the std::less specialization.
366 const llvm::rdf::PhysicalRegisterInfo *PRI;
367 };
368
369 } // namespace std
370
371 namespace llvm::rdf {
372 using RegisterSet = std::set<RegisterRef, std::less<RegisterRef>>;
373 } // namespace llvm::rdf
374
375 #endif // LLVM_CODEGEN_RDFREGISTERS_H
376