LLVM 17.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"
15#include "llvm/MC/LaneBitmask.h"
16#include <cassert>
17#include <cstdint>
18#include <map>
19#include <set>
20#include <vector>
21
22namespace llvm {
23
24class MachineFunction;
25class raw_ostream;
26
27namespace rdf {
28
30
31 // Template class for a map translating uint32_t into arbitrary types.
32 // The map will act like an indexed set: upon insertion of a new object,
33 // it will automatically assign a new index to it. Index of 0 is treated
34 // as invalid and is never allocated.
35 template <typename T, unsigned N = 32>
36 struct IndexedSet {
37 IndexedSet() { Map.reserve(N); }
38
39 T get(uint32_t Idx) const {
40 // Index Idx corresponds to Map[Idx-1].
41 assert(Idx != 0 && !Map.empty() && Idx-1 < Map.size());
42 return Map[Idx-1];
43 }
44
46 // Linear search.
47 auto F = llvm::find(Map, Val);
48 if (F != Map.end())
49 return F - Map.begin() + 1;
50 Map.push_back(Val);
51 return Map.size(); // Return actual_index + 1.
52 }
53
54 uint32_t find(T Val) const {
55 auto F = llvm::find(Map, Val);
56 assert(F != Map.end());
57 return F - Map.begin() + 1;
58 }
59
60 uint32_t size() const { return Map.size(); }
61
62 using const_iterator = typename std::vector<T>::const_iterator;
63
64 const_iterator begin() const { return Map.begin(); }
65 const_iterator end() const { return Map.end(); }
66
67 private:
68 std::vector<T> Map;
69 };
70
71 struct RegisterRef {
74
75 RegisterRef() = default;
77 : Reg(R), Mask(R != 0 ? M : LaneBitmask::getNone()) {}
78
79 operator bool() const {
80 return Reg != 0 && Mask.any();
81 }
82
83 bool operator== (const RegisterRef &RR) const {
84 return Reg == RR.Reg && Mask == RR.Mask;
85 }
86
87 bool operator!= (const RegisterRef &RR) const {
88 return !operator==(RR);
89 }
90
91 bool operator< (const RegisterRef &RR) const {
92 return Reg < RR.Reg || (Reg == RR.Reg && Mask < RR.Mask);
93 }
94
95 size_t hash() const {
96 return std::hash<RegisterId>{}(Reg) ^
97 std::hash<LaneBitmask::Type>{}(Mask.getAsInteger());
98 }
99 };
100
101
104 const MachineFunction &mf);
105
106 static bool isRegMaskId(RegisterId R) {
107 return Register::isStackSlot(R);
108 }
109
111 return Register::index2StackSlot(RegMasks.find(RM));
112 }
113
115 return RegMasks.get(Register::stackSlot2Index(R));
116 }
117
118 bool alias(RegisterRef RA, RegisterRef RB) const {
119 if (!isRegMaskId(RA.Reg))
120 return !isRegMaskId(RB.Reg) ? aliasRR(RA, RB) : aliasRM(RA, RB);
121 return !isRegMaskId(RB.Reg) ? aliasRM(RB, RA) : aliasMM(RA, RB);
122 }
123
124 std::set<RegisterId> getAliasSet(RegisterId Reg) const;
125
127 return RegisterRef(UnitInfos[U].Reg, UnitInfos[U].Mask);
128 }
129
130 const BitVector &getMaskUnits(RegisterId MaskId) const {
131 return MaskInfos[Register::stackSlot2Index(MaskId)].Units;
132 }
133
135 return AliasInfos[U].Regs;
136 }
137
138 RegisterRef mapTo(RegisterRef RR, unsigned R) const;
139 const TargetRegisterInfo &getTRI() const { return TRI; }
140
141 private:
142 struct RegInfo {
143 const TargetRegisterClass *RegClass = nullptr;
144 };
145 struct UnitInfo {
146 RegisterId Reg = 0;
147 LaneBitmask Mask;
148 };
149 struct MaskInfo {
150 BitVector Units;
151 };
152 struct AliasInfo {
153 BitVector Regs;
154 };
155
156 const TargetRegisterInfo &TRI;
157 IndexedSet<const uint32_t*> RegMasks;
158 std::vector<RegInfo> RegInfos;
159 std::vector<UnitInfo> UnitInfos;
160 std::vector<MaskInfo> MaskInfos;
161 std::vector<AliasInfo> AliasInfos;
162
163 bool aliasRR(RegisterRef RA, RegisterRef RB) const;
164 bool aliasRM(RegisterRef RR, RegisterRef RM) const;
165 bool aliasMM(RegisterRef RM, RegisterRef RN) const;
166 };
167
170 : Units(pri.getTRI().getNumRegUnits()), PRI(pri) {}
171 RegisterAggr(const RegisterAggr &RG) = default;
172
173 unsigned count() const { return Units.count(); }
174 bool empty() const { return Units.none(); }
175 bool hasAliasOf(RegisterRef RR) const;
176 bool hasCoverOf(RegisterRef RR) const;
177
178 bool operator==(const RegisterAggr &A) const {
179 return DenseMapInfo<BitVector>::isEqual(Units, A.Units);
180 }
181
183 const PhysicalRegisterInfo &PRI) {
184 return RegisterAggr(PRI).insert(RA).hasCoverOf(RB);
185 }
186
188 RegisterAggr &insert(const RegisterAggr &RG);
192 RegisterAggr &clear(const RegisterAggr &RG);
193
196 RegisterRef makeRegRef() const;
197
198 size_t hash() const {
200 }
201
202 void print(raw_ostream &OS) const;
203
204 struct rr_iterator {
205 using MapType = std::map<RegisterId, LaneBitmask>;
206
207 private:
208 MapType Masks;
209 MapType::iterator Pos;
210 unsigned Index;
211 const RegisterAggr *Owner;
212
213 public:
214 rr_iterator(const RegisterAggr &RG, bool End);
215
217 return RegisterRef(Pos->first, Pos->second);
218 }
219
221 ++Pos;
222 ++Index;
223 return *this;
224 }
225
226 bool operator==(const rr_iterator &I) const {
227 assert(Owner == I.Owner);
228 (void)Owner;
229 return Index == I.Index;
230 }
231
232 bool operator!=(const rr_iterator &I) const {
233 return !(*this == I);
234 }
235 };
236
238 return rr_iterator(*this, false);
239 }
241 return rr_iterator(*this, true);
242 }
243
244 private:
245 BitVector Units;
246 const PhysicalRegisterInfo &PRI;
247 };
248
249 // Optionally print the lane mask, if it is not ~0.
253 };
255
257} // end namespace rdf
258
259} // end namespace llvm
260
261namespace std {
262 template <> struct hash<llvm::rdf::RegisterRef> {
264 return A.hash();
265 }
266 };
267 template <> struct hash<llvm::rdf::RegisterAggr> {
268 size_t operator()(const llvm::rdf::RegisterAggr &A) const {
269 return A.hash();
270 }
271 };
272 template <> struct equal_to<llvm::rdf::RegisterAggr> {
274 const llvm::rdf::RegisterAggr &B) const {
275 return A == B;
276 }
277 };
278}
279#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:464
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
bool none() const
none - Returns true if none of the bits are set.
Definition: BitVector.h:188
static bool isStackSlot(unsigned Reg)
isStackSlot - Sometimes it is useful the be able to store a non-negative frame index in a variable th...
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
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
raw_ostream & operator<<(raw_ostream &OS, const Print< RegisterRef > &P)
Definition: RDFGraph.cpp:55
uint32_t RegisterId
Definition: RDFRegisters.h:29
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:1839
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:51
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:65
typename std::vector< T >::const_iterator const_iterator
Definition: RDFRegisters.h:62
T get(uint32_t Idx) const
Definition: RDFRegisters.h:39
uint32_t size() const
Definition: RDFRegisters.h:60
uint32_t insert(T Val)
Definition: RDFRegisters.h:45
const_iterator begin() const
Definition: RDFRegisters.h:64
uint32_t find(T Val) const
Definition: RDFRegisters.h:54
const BitVector & getMaskUnits(RegisterId MaskId) const
Definition: RDFRegisters.h:130
RegisterId getRegMaskId(const uint32_t *RM) const
Definition: RDFRegisters.h:110
const TargetRegisterInfo & getTRI() const
Definition: RDFRegisters.h:139
static bool isRegMaskId(RegisterId R)
Definition: RDFRegisters.h:106
const uint32_t * getRegMaskBits(RegisterId R) const
Definition: RDFRegisters.h:114
const BitVector & getUnitAliases(uint32_t U) const
Definition: RDFRegisters.h:134
bool alias(RegisterRef RA, RegisterRef RB) const
Definition: RDFRegisters.h:118
std::set< RegisterId > getAliasSet(RegisterId Reg) const
RegisterRef mapTo(RegisterRef RR, unsigned R) const
RegisterRef getRefForUnit(uint32_t U) const
Definition: RDFRegisters.h:126
PrintLaneMaskOpt(LaneBitmask M)
Definition: RDFRegisters.h:251
bool operator!=(const rr_iterator &I) const
Definition: RDFRegisters.h:232
bool operator==(const rr_iterator &I) const
Definition: RDFRegisters.h:226
std::map< RegisterId, LaneBitmask > MapType
Definition: RDFRegisters.h:205
rr_iterator rr_end() const
Definition: RDFRegisters.h:240
RegisterAggr & insert(RegisterRef RR)
bool hasAliasOf(RegisterRef RR) const
bool hasCoverOf(RegisterRef RR) const
RegisterAggr(const PhysicalRegisterInfo &pri)
Definition: RDFRegisters.h:169
unsigned count() const
Definition: RDFRegisters.h:173
RegisterAggr(const RegisterAggr &RG)=default
RegisterRef clearIn(RegisterRef RR) const
void print(raw_ostream &OS) const
bool operator==(const RegisterAggr &A) const
Definition: RDFRegisters.h:178
RegisterRef makeRegRef() const
RegisterRef intersectWith(RegisterRef RR) const
rr_iterator rr_begin() const
Definition: RDFRegisters.h:237
RegisterAggr & intersect(RegisterRef RR)
RegisterAggr & clear(RegisterRef RR)
static bool isCoverOf(RegisterRef RA, RegisterRef RB, const PhysicalRegisterInfo &PRI)
Definition: RDFRegisters.h:182
bool operator<(const RegisterRef &RR) const
Definition: RDFRegisters.h:91
bool operator==(const RegisterRef &RR) const
Definition: RDFRegisters.h:83
bool operator!=(const RegisterRef &RR) const
Definition: RDFRegisters.h:87
size_t hash() const
Definition: RDFRegisters.h:95
RegisterRef(RegisterId R, LaneBitmask M=LaneBitmask::getAll())
Definition: RDFRegisters.h:76
bool operator()(const llvm::rdf::RegisterAggr &A, const llvm::rdf::RegisterAggr &B) const
Definition: RDFRegisters.h:273
size_t operator()(const llvm::rdf::RegisterAggr &A) const
Definition: RDFRegisters.h:268
size_t operator()(llvm::rdf::RegisterRef A) const
Definition: RDFRegisters.h:263