LLVM 17.0.0git
RDFRegisters.cpp
Go to the documentation of this file.
1//===- RDFRegisters.cpp ---------------------------------------------------===//
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
15#include "llvm/MC/LaneBitmask.h"
19#include <cassert>
20#include <cstdint>
21#include <set>
22#include <utility>
23
24using namespace llvm;
25using namespace rdf;
26
28 const MachineFunction &mf)
29 : TRI(tri) {
30 RegInfos.resize(TRI.getNumRegs());
31
32 BitVector BadRC(TRI.getNumRegs());
33 for (const TargetRegisterClass *RC : TRI.regclasses()) {
34 for (MCPhysReg R : *RC) {
35 RegInfo &RI = RegInfos[R];
36 if (RI.RegClass != nullptr && !BadRC[R]) {
37 if (RC->LaneMask != RI.RegClass->LaneMask) {
38 BadRC.set(R);
39 RI.RegClass = nullptr;
40 }
41 } else
42 RI.RegClass = RC;
43 }
44 }
45
46 UnitInfos.resize(TRI.getNumRegUnits());
47
48 for (uint32_t U = 0, NU = TRI.getNumRegUnits(); U != NU; ++U) {
49 if (UnitInfos[U].Reg != 0)
50 continue;
51 MCRegUnitRootIterator R(U, &TRI);
52 assert(R.isValid());
53 RegisterId F = *R;
54 ++R;
55 if (R.isValid()) {
56 UnitInfos[U].Mask = LaneBitmask::getAll();
57 UnitInfos[U].Reg = F;
58 } else {
59 for (MCRegUnitMaskIterator I(F, &TRI); I.isValid(); ++I) {
60 std::pair<uint32_t,LaneBitmask> P = *I;
61 UnitInfo &UI = UnitInfos[P.first];
62 UI.Reg = F;
63 if (P.second.any()) {
64 UI.Mask = P.second;
65 } else {
66 if (const TargetRegisterClass *RC = RegInfos[F].RegClass)
67 UI.Mask = RC->LaneMask;
68 else
69 UI.Mask = LaneBitmask::getAll();
70 }
71 }
72 }
73 }
74
75 for (const uint32_t *RM : TRI.getRegMasks())
76 RegMasks.insert(RM);
77 for (const MachineBasicBlock &B : mf)
78 for (const MachineInstr &In : B)
79 for (const MachineOperand &Op : In.operands())
80 if (Op.isRegMask())
81 RegMasks.insert(Op.getRegMask());
82
83 MaskInfos.resize(RegMasks.size()+1);
84 for (uint32_t M = 1, NM = RegMasks.size(); M <= NM; ++M) {
85 BitVector PU(TRI.getNumRegUnits());
86 const uint32_t *MB = RegMasks.get(M);
87 for (unsigned I = 1, E = TRI.getNumRegs(); I != E; ++I) {
88 if (!(MB[I / 32] & (1u << (I % 32))))
89 continue;
90 for (MCRegUnitIterator U(MCRegister::from(I), &TRI); U.isValid(); ++U)
91 PU.set(*U);
92 }
93 MaskInfos[M].Units = PU.flip();
94 }
95
96 AliasInfos.resize(TRI.getNumRegUnits());
97 for (uint32_t U = 0, NU = TRI.getNumRegUnits(); U != NU; ++U) {
98 BitVector AS(TRI.getNumRegs());
99 for (MCRegUnitRootIterator R(U, &TRI); R.isValid(); ++R)
100 for (MCPhysReg S : TRI.superregs_inclusive(*R))
101 AS.set(S);
102 AliasInfos[U].Regs = AS;
103 }
104}
105
106std::set<RegisterId> PhysicalRegisterInfo::getAliasSet(RegisterId Reg) const {
107 // Do not include RR in the alias set.
108 std::set<RegisterId> AS;
110 if (isRegMaskId(Reg)) {
111 // XXX SLOW
112 const uint32_t *MB = getRegMaskBits(Reg);
113 for (unsigned i = 1, e = TRI.getNumRegs(); i != e; ++i) {
114 if (MB[i/32] & (1u << (i%32)))
115 continue;
116 AS.insert(i);
117 }
118 for (const uint32_t *RM : RegMasks) {
120 if (MI != Reg && aliasMM(RegisterRef(Reg), RegisterRef(MI)))
121 AS.insert(MI);
122 }
123 return AS;
124 }
125
126 for (MCRegAliasIterator AI(Reg, &TRI, false); AI.isValid(); ++AI)
127 AS.insert(*AI);
128 for (const uint32_t *RM : RegMasks) {
130 if (aliasRM(RegisterRef(Reg), RegisterRef(MI)))
131 AS.insert(MI);
132 }
133 return AS;
134}
135
136bool PhysicalRegisterInfo::aliasRR(RegisterRef RA, RegisterRef RB) const {
139
140 MCRegUnitMaskIterator UMA(RA.Reg, &TRI);
141 MCRegUnitMaskIterator UMB(RB.Reg, &TRI);
142 // Reg units are returned in the numerical order.
143 while (UMA.isValid() && UMB.isValid()) {
144 // Skip units that are masked off in RA.
145 std::pair<RegisterId,LaneBitmask> PA = *UMA;
146 if (PA.second.any() && (PA.second & RA.Mask).none()) {
147 ++UMA;
148 continue;
149 }
150 // Skip units that are masked off in RB.
151 std::pair<RegisterId,LaneBitmask> PB = *UMB;
152 if (PB.second.any() && (PB.second & RB.Mask).none()) {
153 ++UMB;
154 continue;
155 }
156
157 if (PA.first == PB.first)
158 return true;
159 if (PA.first < PB.first)
160 ++UMA;
161 else if (PB.first < PA.first)
162 ++UMB;
163 }
164 return false;
165}
166
167bool PhysicalRegisterInfo::aliasRM(RegisterRef RR, RegisterRef RM) const {
169 const uint32_t *MB = getRegMaskBits(RM.Reg);
170 bool Preserved = MB[RR.Reg/32] & (1u << (RR.Reg%32));
171 // If the lane mask information is "full", e.g. when the given lane mask
172 // is a superset of the lane mask from the register class, check the regmask
173 // bit directly.
174 if (RR.Mask == LaneBitmask::getAll())
175 return !Preserved;
176 const TargetRegisterClass *RC = RegInfos[RR.Reg].RegClass;
177 if (RC != nullptr && (RR.Mask & RC->LaneMask) == RC->LaneMask)
178 return !Preserved;
179
180 // Otherwise, check all subregisters whose lane mask overlaps the given
181 // mask. For each such register, if it is preserved by the regmask, then
182 // clear the corresponding bits in the given mask. If at the end, all
183 // bits have been cleared, the register does not alias the regmask (i.e.
184 // is it preserved by it).
185 LaneBitmask M = RR.Mask;
186 for (MCSubRegIndexIterator SI(RR.Reg, &TRI); SI.isValid(); ++SI) {
187 LaneBitmask SM = TRI.getSubRegIndexLaneMask(SI.getSubRegIndex());
188 if ((SM & RR.Mask).none())
189 continue;
190 unsigned SR = SI.getSubReg();
191 if (!(MB[SR/32] & (1u << (SR%32))))
192 continue;
193 // The subregister SR is preserved.
194 M &= ~SM;
195 if (M.none())
196 return false;
197 }
198
199 return true;
200}
201
202bool PhysicalRegisterInfo::aliasMM(RegisterRef RM, RegisterRef RN) const {
203 assert(isRegMaskId(RM.Reg) && isRegMaskId(RN.Reg));
204 unsigned NumRegs = TRI.getNumRegs();
205 const uint32_t *BM = getRegMaskBits(RM.Reg);
206 const uint32_t *BN = getRegMaskBits(RN.Reg);
207
208 for (unsigned w = 0, nw = NumRegs/32; w != nw; ++w) {
209 // Intersect the negations of both words. Disregard reg=0,
210 // i.e. 0th bit in the 0th word.
211 uint32_t C = ~BM[w] & ~BN[w];
212 if (w == 0)
213 C &= ~1;
214 if (C)
215 return true;
216 }
217
218 // Check the remaining registers in the last word.
219 unsigned TailRegs = NumRegs % 32;
220 if (TailRegs == 0)
221 return false;
222 unsigned TW = NumRegs / 32;
223 uint32_t TailMask = (1u << TailRegs) - 1;
224 if (~BM[TW] & ~BN[TW] & TailMask)
225 return true;
226
227 return false;
228}
229
231 if (RR.Reg == R)
232 return RR;
233 if (unsigned Idx = TRI.getSubRegIndex(R, RR.Reg))
235 if (unsigned Idx = TRI.getSubRegIndex(RR.Reg, R)) {
236 const RegInfo &RI = RegInfos[R];
237 LaneBitmask RCM = RI.RegClass ? RI.RegClass->LaneMask
240 return RegisterRef(R, M & RCM);
241 }
242 llvm_unreachable("Invalid arguments: unrelated registers?");
243}
244
247 return Units.anyCommon(PRI.getMaskUnits(RR.Reg));
248
249 for (MCRegUnitMaskIterator U(RR.Reg, &PRI.getTRI()); U.isValid(); ++U) {
250 std::pair<uint32_t,LaneBitmask> P = *U;
251 if (P.second.none() || (P.second & RR.Mask).any())
252 if (Units.test(P.first))
253 return true;
254 }
255 return false;
256}
257
260 BitVector T(PRI.getMaskUnits(RR.Reg));
261 return T.reset(Units).none();
262 }
263
264 for (MCRegUnitMaskIterator U(RR.Reg, &PRI.getTRI()); U.isValid(); ++U) {
265 std::pair<uint32_t,LaneBitmask> P = *U;
266 if (P.second.none() || (P.second & RR.Mask).any())
267 if (!Units.test(P.first))
268 return false;
269 }
270 return true;
271}
272
275 Units |= PRI.getMaskUnits(RR.Reg);
276 return *this;
277 }
278
279 for (MCRegUnitMaskIterator U(RR.Reg, &PRI.getTRI()); U.isValid(); ++U) {
280 std::pair<uint32_t,LaneBitmask> P = *U;
281 if (P.second.none() || (P.second & RR.Mask).any())
282 Units.set(P.first);
283 }
284 return *this;
285}
286
288 Units |= RG.Units;
289 return *this;
290}
291
293 return intersect(RegisterAggr(PRI).insert(RR));
294}
295
297 Units &= RG.Units;
298 return *this;
299}
300
302 return clear(RegisterAggr(PRI).insert(RR));
303}
304
306 Units.reset(RG.Units);
307 return *this;
308}
309
311 RegisterAggr T(PRI);
312 T.insert(RR).intersect(*this);
313 if (T.empty())
314 return RegisterRef();
315 RegisterRef NR = T.makeRegRef();
316 assert(NR);
317 return NR;
318}
319
321 return RegisterAggr(PRI).insert(RR).clear(*this).makeRegRef();
322}
323
325 int U = Units.find_first();
326 if (U < 0)
327 return RegisterRef();
328
329 // Find the set of all registers that are aliased to all the units
330 // in this aggregate.
331
332 // Get all the registers aliased to the first unit in the bit vector.
333 BitVector Regs = PRI.getUnitAliases(U);
334 U = Units.find_next(U);
335
336 // For each other unit, intersect it with the set of all registers
337 // aliased that unit.
338 while (U >= 0) {
339 Regs &= PRI.getUnitAliases(U);
340 U = Units.find_next(U);
341 }
342
343 // If there is at least one register remaining, pick the first one,
344 // and consolidate the masks of all of its units contained in this
345 // aggregate.
346
347 int F = Regs.find_first();
348 if (F <= 0)
349 return RegisterRef();
350
351 LaneBitmask M;
352 for (MCRegUnitMaskIterator I(F, &PRI.getTRI()); I.isValid(); ++I) {
353 std::pair<uint32_t,LaneBitmask> P = *I;
354 if (Units.test(P.first))
355 M |= P.second.none() ? LaneBitmask::getAll() : P.second;
356 }
357 return RegisterRef(F, M);
358}
359
361 OS << '{';
362 for (int U = Units.find_first(); U >= 0; U = Units.find_next(U))
363 OS << ' ' << printRegUnit(U, &PRI.getTRI());
364 OS << " }";
365}
366
368 bool End)
369 : Owner(&RG) {
370 for (int U = RG.Units.find_first(); U >= 0; U = RG.Units.find_next(U)) {
371 RegisterRef R = RG.PRI.getRefForUnit(U);
372 Masks[R.Reg] |= R.Mask;
373 }
374 Pos = End ? Masks.end() : Masks.begin();
375 Index = End ? Masks.size() : 0;
376}
377
379 A.print(OS);
380 return OS;
381}
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")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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
IRTranslator LLVM IR MI
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 const TargetRegisterInfo * TRI
#define P(N)
PassBuilder PB(Machine, PassOpts->PTO, std::nullopt, &PIC)
@ SI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI optimize exec mask operations pre RA
raw_pwrite_stream & OS
bool test(unsigned Idx) const
Definition: BitVector.h:461
BitVector & reset()
Definition: BitVector.h:392
int find_first() const
find_first - Returns the index of the first set bit, -1 if none of the bits are set.
Definition: BitVector.h:300
bool anyCommon(const BitVector &RHS) const
Test if any common bits are set.
Definition: BitVector.h:489
BitVector & set()
Definition: BitVector.h:351
BitVector & flip()
Definition: BitVector.h:431
int find_next(unsigned Prev) const
find_next - Returns the index of the next set bit following the "Prev" bit.
Definition: BitVector.h:308
MCRegAliasIterator enumerates all registers aliasing Reg.
MCRegUnitMaskIterator enumerates a list of register units and their associated lane masks for Reg.
MCRegUnitRootIterator enumerates the root registers of a register unit.
unsigned getNumRegUnits() const
Return the number of (native) register units in the target.
iterator_range< mc_superreg_iterator > superregs_inclusive(MCRegister Reg) const
Return an iterator range over all super-registers of Reg, including Reg.
unsigned getSubRegIndex(MCRegister RegNo, MCRegister SubRegNo) const
For a given register pair, return the sub-register index if the second register is a sub-register of ...
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
static MCRegister from(unsigned Val)
Check the provided unsigned value is a valid MCRegister.
Definition: MCRegister.h:65
Iterator that enumerates the sub-registers of a Reg and the associated sub-register indices.
Representation of each machine instruction.
Definition: MachineInstr.h:68
MachineOperand class - Representation of each machine instruction operand.
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...
iterator_range< regclass_iterator > regclasses() const
virtual ArrayRef< const uint32_t * > getRegMasks() const =0
Return all the call-preserved register masks defined for this target.
LaneBitmask reverseComposeSubRegIndexLaneMask(unsigned IdxA, LaneBitmask LaneMask) const
Transform a lanemask given for a virtual register to the corresponding lanemask before using subregis...
LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const
Return a bitmask representing the parts of a register that are covered by SubIdx.
LaneBitmask composeSubRegIndexLaneMask(unsigned IdxA, LaneBitmask Mask) const
Transforms a LaneMask computed for one subregister to the lanemask that would have been computed when...
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
raw_ostream & operator<<(raw_ostream &OS, const Print< RegisterRef > &P)
Definition: RDFGraph.cpp:55
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Printable printRegUnit(unsigned Unit, const TargetRegisterInfo *TRI)
Create Printable object to print register units on a raw_ostream.
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:82
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 BitVector & getMaskUnits(RegisterId MaskId) const
Definition: RDFRegisters.h:130
RegisterId getRegMaskId(const uint32_t *RM) const
Definition: RDFRegisters.h:110
PhysicalRegisterInfo(const TargetRegisterInfo &tri, const MachineFunction &mf)
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
std::set< RegisterId > getAliasSet(RegisterId Reg) const
RegisterRef mapTo(RegisterRef RR, unsigned R) const
RegisterRef getRefForUnit(uint32_t U) const
Definition: RDFRegisters.h:126
rr_iterator(const RegisterAggr &RG, bool End)
RegisterAggr & insert(RegisterRef RR)
bool hasAliasOf(RegisterRef RR) const
bool hasCoverOf(RegisterRef RR) const
RegisterRef clearIn(RegisterRef RR) const
void print(raw_ostream &OS) const
RegisterRef makeRegRef() const
RegisterRef intersectWith(RegisterRef RR) const
RegisterAggr & intersect(RegisterRef RR)
RegisterAggr & clear(RegisterRef RR)