LLVM 20.0.0git
RDFRegisters.h
Go to the documentation of this file.
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"
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
24namespace llvm {
25
26class MachineFunction;
27class raw_ostream;
28
29namespace rdf {
30struct RegisterAggr;
31
33
34template <typename T>
35bool 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.
53template <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
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
84private:
85 std::vector<T> Map;
86};
87
90 LaneBitmask Mask = LaneBitmask::getNone(); // Only for registers.
91
92 constexpr RegisterRef() = default;
93 constexpr explicit RegisterRef(RegisterId R,
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) {
115 }
116 static constexpr bool isUnitId(unsigned Id) {
118 }
119 static constexpr bool isMaskId(unsigned Id) {
120 return Register::isStackSlot(Id);
121 }
122
123 static constexpr RegisterId toUnitId(unsigned Idx) {
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
143 const MachineFunction &mf);
144
146 return Register::index2StackSlot(RegMasks.find(RM));
147 }
148
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
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
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
181private:
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
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
221 const PhysicalRegisterInfo &PRI) {
222 return RegisterAggr(PRI).insert(RA).hasCoverOf(RB);
223 }
224
226 RegisterAggr &insert(const RegisterAggr &RG);
230 RegisterAggr &clear(const RegisterAggr &RG);
231
234 RegisterRef makeRegRef() const;
235
236 size_t hash() const { return DenseMapInfo<BitVector>::getHashValue(Units); }
237
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
251 return RegisterRef(Pos->first, Pos->second);
252 }
253
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
273 unit_iterator unit_begin() const { return Units.set_bits_begin(); }
274 unit_iterator unit_end() const { return Units.set_bits_end(); }
275
277 return make_range(ref_begin(), ref_end());
278 }
280 return make_range(unit_begin(), unit_end());
281 }
282
283private:
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 [].
290template <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
303private:
304 RegisterAggr Empty;
305 std::map<KeyType, RegisterAggr> Map;
306
307public:
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
314
315// Print the lane mask in a short form (or not at all if all bits are set).
319};
321
322} // end namespace rdf
323} // end namespace llvm
324
325namespace std {
326
327template <> struct hash<llvm::rdf::RegisterRef> {
329 return A.hash();
330 }
331};
332
333template <> struct hash<llvm::rdf::RegisterAggr> {
334 size_t operator()(const llvm::rdf::RegisterAggr &A) const { //
335 return A.hash();
336 }
337};
338
339template <> struct equal_to<llvm::rdf::RegisterRef> {
340 constexpr equal_to(const llvm::rdf::PhysicalRegisterInfo &pri) : PRI(&pri) {}
341
343 return PRI->equal_to(A, B);
344 }
345
346private:
347 // Make it a pointer just in case. See comment in `less` below.
349};
350
351template <> struct equal_to<llvm::rdf::RegisterAggr> {
353 const llvm::rdf::RegisterAggr &B) const {
354 return A == B;
355 }
356};
357
358template <> struct less<llvm::rdf::RegisterRef> {
359 constexpr less(const llvm::rdf::PhysicalRegisterInfo &pri) : PRI(&pri) {}
360
362 return PRI->less(A, B);
363 }
364
365private:
366 // Make it a pointer because apparently some versions of MSVC use std::swap
367 // on the std::less specialization.
369};
370
371} // namespace std
372
373namespace llvm::rdf {
374using RegisterSet = std::set<RegisterRef, std::less<RegisterRef>>;
375} // namespace llvm::rdf
376
377#endif // LLVM_CODEGEN_RDFREGISTERS_H
This file implements the BitVector class.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
bool End
Definition: ELF_riscv.cpp:480
A common definition of LaneBitmask for use in TableGen and CodeGen.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned Reg
#define P(N)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI optimize exec mask operations pre RA
This file contains some templates that are useful if you are working with the STL at all.
raw_pwrite_stream & OS
size_type count() const
count - Returns the number of bits which are set.
Definition: BitVector.h:162
const_set_bits_iterator set_bits_end() const
Definition: BitVector.h:137
const_set_bits_iterator_impl< BitVector > const_set_bits_iterator
Definition: BitVector.h:131
bool none() const
none - Returns true if none of the bits are set.
Definition: BitVector.h:188
const_set_bits_iterator set_bits_begin() const
Definition: BitVector.h:134
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:33
static constexpr unsigned VirtualRegFlag
Definition: MCRegister.h:55
static constexpr bool isStackSlot(unsigned Reg)
isStackSlot - Sometimes it is useful to be able to store a non-negative frame index in a variable tha...
Definition: Register.h:44
static int stackSlot2Index(Register Reg)
Compute the frame index from a register value representing a stack slot.
Definition: Register.h:52
static Register index2StackSlot(int FI)
Convert a non-negative frame index to a stack slot register value.
Definition: Register.h:58
static constexpr bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:71
static constexpr bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:65
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
std::set< RegisterRef > RegisterSet
Definition: RDFGraph.h:450
raw_ostream & operator<<(raw_ostream &OS, const Print< RegisterRef > &P)
Definition: RDFGraph.cpp:45
uint32_t RegisterId
Definition: RDFRegisters.h:32
bool disjoint(const std::set< T > &A, const std::set< T > &B)
Definition: RDFRegisters.h:35
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1742
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
#define N
An information struct used to provide DenseMap with the various necessary components for a given valu...
Definition: DenseMapInfo.h:52
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:82
constexpr bool any() const
Definition: LaneBitmask.h:53
static constexpr LaneBitmask getNone()
Definition: LaneBitmask.h:81
constexpr Type getAsInteger() const
Definition: LaneBitmask.h:74
const_iterator end() const
Definition: RDFRegisters.h:82
typename std::vector< T >::const_iterator const_iterator
Definition: RDFRegisters.h:79
T get(uint32_t Idx) const
Definition: RDFRegisters.h:56
uint32_t size() const
Definition: RDFRegisters.h:77
uint32_t insert(T Val)
Definition: RDFRegisters.h:62
const_iterator begin() const
Definition: RDFRegisters.h:81
uint32_t find(T Val) const
Definition: RDFRegisters.h:71
const BitVector & getMaskUnits(RegisterId MaskId) const
Definition: RDFRegisters.h:162
RegisterId getRegMaskId(const uint32_t *RM) const
Definition: RDFRegisters.h:145
void print(raw_ostream &OS, RegisterRef A) const
const TargetRegisterInfo & getTRI() const
Definition: RDFRegisters.h:173
const uint32_t * getRegMaskBits(RegisterId R) const
Definition: RDFRegisters.h:149
std::set< RegisterId > getAliasSet(RegisterId Reg) const
const BitVector & getUnitAliases(uint32_t U) const
Definition: RDFRegisters.h:168
bool equal_to(RegisterRef A, RegisterRef B) const
bool alias(RegisterRef RA, RegisterRef RB) const
RegisterRef mapTo(RegisterRef RR, unsigned R) const
bool less(RegisterRef A, RegisterRef B) const
std::set< RegisterId > getUnits(RegisterRef RR) const
RegisterRef getRefForUnit(uint32_t U) const
Definition: RDFRegisters.h:158
PrintLaneMaskShort(LaneBitmask M)
Definition: RDFRegisters.h:317
RegisterAggrMap(const PhysicalRegisterInfo &pri)
Definition: RDFRegisters.h:291
auto find(const KeyType &Key) const
Definition: RDFRegisters.h:301
typename decltype(Map)::mapped_type mapped_type
Definition: RDFRegisters.h:309
typename decltype(Map)::key_type key_type
Definition: RDFRegisters.h:308
RegisterAggr & operator[](KeyType Key)
Definition: RDFRegisters.h:293
typename decltype(Map)::value_type value_type
Definition: RDFRegisters.h:310
std::map< RegisterId, LaneBitmask > MapType
Definition: RDFRegisters.h:239
bool operator!=(const ref_iterator &I) const
Definition: RDFRegisters.h:266
bool operator==(const ref_iterator &I) const
Definition: RDFRegisters.h:260
iterator_range< ref_iterator > refs() const
Definition: RDFRegisters.h:276
RegisterAggr & insert(RegisterRef RR)
iterator_range< unit_iterator > units() const
Definition: RDFRegisters.h:279
RegisterAggr(const PhysicalRegisterInfo &pri)
Definition: RDFRegisters.h:205
unsigned size() const
Definition: RDFRegisters.h:209
const PhysicalRegisterInfo & getPRI() const
Definition: RDFRegisters.h:214
RegisterRef clearIn(RegisterRef RR) const
unit_iterator unit_end() const
Definition: RDFRegisters.h:274
RegisterAggr(const RegisterAggr &RG)=default
RegisterAggr & clear(RegisterRef RR)
ref_iterator ref_begin() const
Definition: RDFRegisters.h:269
RegisterRef makeRegRef() const
RegisterAggr & intersect(RegisterRef RR)
bool hasAliasOf(RegisterRef RR) const
RegisterRef intersectWith(RegisterRef RR) const
bool operator==(const RegisterAggr &A) const
Definition: RDFRegisters.h:216
bool hasCoverOf(RegisterRef RR) const
unit_iterator unit_begin() const
Definition: RDFRegisters.h:273
static bool isCoverOf(RegisterRef RA, RegisterRef RB, const PhysicalRegisterInfo &PRI)
Definition: RDFRegisters.h:220
ref_iterator ref_end() const
Definition: RDFRegisters.h:270
typename BitVector::const_set_bits_iterator unit_iterator
Definition: RDFRegisters.h:272
constexpr unsigned idx() const
Definition: RDFRegisters.h:102
constexpr RegisterRef(RegisterId R, LaneBitmask M=LaneBitmask::getAll())
Definition: RDFRegisters.h:93
bool operator!=(RegisterRef) const =delete
static constexpr RegisterId toUnitId(unsigned Idx)
Definition: RDFRegisters.h:123
constexpr RegisterRef()=default
constexpr bool isReg() const
Definition: RDFRegisters.h:98
constexpr bool isMask() const
Definition: RDFRegisters.h:100
static constexpr bool isMaskId(unsigned Id)
Definition: RDFRegisters.h:119
static constexpr bool isRegId(unsigned Id)
Definition: RDFRegisters.h:113
static constexpr bool isUnitId(unsigned Id)
Definition: RDFRegisters.h:116
constexpr bool isUnit() const
Definition: RDFRegisters.h:99
static constexpr unsigned toIdx(RegisterId Id)
Definition: RDFRegisters.h:127
size_t hash() const
Definition: RDFRegisters.h:108
bool operator<(RegisterRef) const =delete
bool operator==(RegisterRef) const =delete
bool operator()(const llvm::rdf::RegisterAggr &A, const llvm::rdf::RegisterAggr &B) const
Definition: RDFRegisters.h:352
bool operator()(llvm::rdf::RegisterRef A, llvm::rdf::RegisterRef B) const
Definition: RDFRegisters.h:342
constexpr equal_to(const llvm::rdf::PhysicalRegisterInfo &pri)
Definition: RDFRegisters.h:340
size_t operator()(const llvm::rdf::RegisterAggr &A) const
Definition: RDFRegisters.h:334
size_t operator()(llvm::rdf::RegisterRef A) const
Definition: RDFRegisters.h:328
bool operator()(llvm::rdf::RegisterRef A, llvm::rdf::RegisterRef B) const
Definition: RDFRegisters.h:361
constexpr less(const llvm::rdf::PhysicalRegisterInfo &pri)
Definition: RDFRegisters.h:359