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
9#include "llvm/ADT/BitVector.h"
10#include "llvm/CodeGen/MachineFunction.h"
11#include "llvm/CodeGen/MachineInstr.h"
12#include "llvm/CodeGen/MachineOperand.h"
13#include "llvm/CodeGen/RDFRegisters.h"
14#include "llvm/CodeGen/TargetRegisterInfo.h"
15#include "llvm/MC/LaneBitmask.h"
16#include "llvm/MC/MCRegisterInfo.h"
17#include "llvm/Support/ErrorHandling.h"
18#include "llvm/Support/Format.h"
19#include "llvm/Support/MathExtras.h"
20#include "llvm/Support/raw_ostream.h"
21#include <cassert>
22#include <cstdint>
23#include <set>
24#include <utility>
25
26namespace llvm::rdf {
27
28PhysicalRegisterInfo::PhysicalRegisterInfo(const TargetRegisterInfo &tri,
29 const MachineFunction &mf)
30 : TRI(tri) {
31 RegInfos.resize(new_size: TRI.getNumRegs());
32
33 BitVector BadRC(TRI.getNumRegs());
34 for (const TargetRegisterClass *RC : TRI.regclasses()) {
35 for (MCPhysReg R : *RC) {
36 RegInfo &RI = RegInfos[R];
37 if (RI.RegClass != nullptr && !BadRC[R]) {
38 if (RC->LaneMask != RI.RegClass->LaneMask) {
39 BadRC.set(R);
40 RI.RegClass = nullptr;
41 }
42 } else
43 RI.RegClass = RC;
44 }
45 }
46
47 UnitInfos.resize(new_size: TRI.getNumRegUnits());
48
49 for (uint32_t U = 0, NU = TRI.getNumRegUnits(); U != NU; ++U) {
50 if (UnitInfos[U].Reg != 0)
51 continue;
52 MCRegUnitRootIterator R(U, &TRI);
53 assert(R.isValid());
54 RegisterId F = *R;
55 ++R;
56 if (R.isValid()) {
57 UnitInfos[U].Mask = LaneBitmask::getAll();
58 UnitInfos[U].Reg = F;
59 } else {
60 for (MCRegUnitMaskIterator I(F, &TRI); I.isValid(); ++I) {
61 std::pair<uint32_t, LaneBitmask> P = *I;
62 UnitInfo &UI = UnitInfos[P.first];
63 UI.Reg = F;
64 UI.Mask = P.second;
65 }
66 }
67 }
68
69 for (const uint32_t *RM : TRI.getRegMasks())
70 RegMasks.insert(Val: RM);
71 for (const MachineBasicBlock &B : mf)
72 for (const MachineInstr &In : B)
73 for (const MachineOperand &Op : In.operands())
74 if (Op.isRegMask())
75 RegMasks.insert(Val: Op.getRegMask());
76
77 MaskInfos.resize(new_size: RegMasks.size() + 1);
78 for (uint32_t M = 1, NM = RegMasks.size(); M <= NM; ++M) {
79 BitVector PU(TRI.getNumRegUnits());
80 const uint32_t *MB = RegMasks.get(Idx: M);
81 for (unsigned I = 1, E = TRI.getNumRegs(); I != E; ++I) {
82 if (!(MB[I / 32] & (1u << (I % 32))))
83 continue;
84 for (MCRegUnit Unit : TRI.regunits(Reg: MCRegister::from(Val: I)))
85 PU.set(Unit);
86 }
87 MaskInfos[M].Units = PU.flip();
88 }
89
90 AliasInfos.resize(new_size: TRI.getNumRegUnits());
91 for (uint32_t U = 0, NU = TRI.getNumRegUnits(); U != NU; ++U) {
92 BitVector AS(TRI.getNumRegs());
93 for (MCRegUnitRootIterator R(U, &TRI); R.isValid(); ++R)
94 for (MCPhysReg S : TRI.superregs_inclusive(Reg: *R))
95 AS.set(S);
96 AliasInfos[U].Regs = AS;
97 }
98}
99
100bool PhysicalRegisterInfo::alias(RegisterRef RA, RegisterRef RB) const {
101 return !disjoint(A: getUnits(RR: RA), B: getUnits(RR: RB));
102}
103
104std::set<RegisterId> PhysicalRegisterInfo::getAliasSet(RegisterId Reg) const {
105 // Do not include Reg in the alias set.
106 std::set<RegisterId> AS;
107 assert(!RegisterRef::isUnitId(Reg) && "No units allowed");
108 if (RegisterRef::isMaskId(Id: Reg)) {
109 // XXX SLOW
110 const uint32_t *MB = getRegMaskBits(R: Reg);
111 for (unsigned i = 1, e = TRI.getNumRegs(); i != e; ++i) {
112 if (MB[i / 32] & (1u << (i % 32)))
113 continue;
114 AS.insert(x: i);
115 }
116 return AS;
117 }
118
119 assert(RegisterRef::isRegId(Reg));
120 for (MCRegAliasIterator AI(Reg, &TRI, false); AI.isValid(); ++AI)
121 AS.insert(x: *AI);
122
123 return AS;
124}
125
126std::set<RegisterId> PhysicalRegisterInfo::getUnits(RegisterRef RR) const {
127 std::set<RegisterId> Units;
128
129 if (RR.Reg == 0)
130 return Units; // Empty
131
132 if (RR.isReg()) {
133 if (RR.Mask.none())
134 return Units; // Empty
135 for (MCRegUnitMaskIterator UM(RR.idx(), &TRI); UM.isValid(); ++UM) {
136 auto [U, M] = *UM;
137 if ((M & RR.Mask).any())
138 Units.insert(x: U);
139 }
140 return Units;
141 }
142
143 assert(RR.isMask());
144 unsigned NumRegs = TRI.getNumRegs();
145 const uint32_t *MB = getRegMaskBits(R: RR.idx());
146 for (unsigned I = 0, E = (NumRegs + 31) / 32; I != E; ++I) {
147 uint32_t C = ~MB[I]; // Clobbered regs
148 if (I == 0) // Reg 0 should be ignored
149 C &= maskLeadingOnes<unsigned>(N: 31);
150 if (I + 1 == E && NumRegs % 32 != 0) // Last word may be partial
151 C &= maskTrailingOnes<unsigned>(N: NumRegs % 32);
152 if (C == 0)
153 continue;
154 while (C != 0) {
155 unsigned T = llvm::countr_zero(Val: C);
156 unsigned CR = 32 * I + T; // Clobbered reg
157 for (MCRegUnit U : TRI.regunits(Reg: CR))
158 Units.insert(x: U);
159 C &= ~(1u << T);
160 }
161 }
162 return Units;
163}
164
165RegisterRef PhysicalRegisterInfo::mapTo(RegisterRef RR, unsigned R) const {
166 if (RR.Reg == R)
167 return RR;
168 if (unsigned Idx = TRI.getSubRegIndex(RegNo: R, SubRegNo: RR.Reg))
169 return RegisterRef(R, TRI.composeSubRegIndexLaneMask(IdxA: Idx, Mask: RR.Mask));
170 if (unsigned Idx = TRI.getSubRegIndex(RegNo: RR.Reg, SubRegNo: R)) {
171 const RegInfo &RI = RegInfos[R];
172 LaneBitmask RCM =
173 RI.RegClass ? RI.RegClass->LaneMask : LaneBitmask::getAll();
174 LaneBitmask M = TRI.reverseComposeSubRegIndexLaneMask(IdxA: Idx, LaneMask: RR.Mask);
175 return RegisterRef(R, M & RCM);
176 }
177 llvm_unreachable("Invalid arguments: unrelated registers?");
178}
179
180bool PhysicalRegisterInfo::equal_to(RegisterRef A, RegisterRef B) const {
181 if (!A.isReg() || !B.isReg()) {
182 // For non-regs, or comparing reg and non-reg, use only the Reg member.
183 return A.Reg == B.Reg;
184 }
185
186 if (A.Reg == B.Reg)
187 return A.Mask == B.Mask;
188
189 // Compare reg units lexicographically.
190 MCRegUnitMaskIterator AI(A.Reg, &getTRI());
191 MCRegUnitMaskIterator BI(B.Reg, &getTRI());
192 while (AI.isValid() && BI.isValid()) {
193 auto [AReg, AMask] = *AI;
194 auto [BReg, BMask] = *BI;
195
196 // If both iterators point to a unit contained in both A and B, then
197 // compare the units.
198 if ((AMask & A.Mask).any() && (BMask & B.Mask).any()) {
199 if (AReg != BReg)
200 return false;
201 // Units are equal, move on to the next ones.
202 ++AI;
203 ++BI;
204 continue;
205 }
206
207 if ((AMask & A.Mask).none())
208 ++AI;
209 if ((BMask & B.Mask).none())
210 ++BI;
211 }
212 // One or both have reached the end.
213 return static_cast<int>(AI.isValid()) == static_cast<int>(BI.isValid());
214}
215
216bool PhysicalRegisterInfo::less(RegisterRef A, RegisterRef B) const {
217 if (!A.isReg() || !B.isReg()) {
218 // For non-regs, or comparing reg and non-reg, use only the Reg member.
219 return A.Reg < B.Reg;
220 }
221
222 if (A.Reg == B.Reg)
223 return A.Mask < B.Mask;
224 if (A.Mask == B.Mask)
225 return A.Reg < B.Reg;
226
227 // Compare reg units lexicographically.
228 llvm::MCRegUnitMaskIterator AI(A.Reg, &getTRI());
229 llvm::MCRegUnitMaskIterator BI(B.Reg, &getTRI());
230 while (AI.isValid() && BI.isValid()) {
231 auto [AReg, AMask] = *AI;
232 auto [BReg, BMask] = *BI;
233
234 // If both iterators point to a unit contained in both A and B, then
235 // compare the units.
236 if ((AMask & A.Mask).any() && (BMask & B.Mask).any()) {
237 if (AReg != BReg)
238 return AReg < BReg;
239 // Units are equal, move on to the next ones.
240 ++AI;
241 ++BI;
242 continue;
243 }
244
245 if ((AMask & A.Mask).none())
246 ++AI;
247 if ((BMask & B.Mask).none())
248 ++BI;
249 }
250 // One or both have reached the end: assume invalid < valid.
251 return static_cast<int>(AI.isValid()) < static_cast<int>(BI.isValid());
252}
253
254void PhysicalRegisterInfo::print(raw_ostream &OS, RegisterRef A) const {
255 if (A.Reg == 0 || A.isReg()) {
256 if (0 < A.idx() && A.idx() < TRI.getNumRegs())
257 OS << TRI.getName(RegNo: A.idx());
258 else
259 OS << printReg(Reg: A.idx(), TRI: &TRI);
260 OS << PrintLaneMaskShort(A.Mask);
261 } else if (A.isUnit()) {
262 OS << printRegUnit(Unit: A.idx(), TRI: &TRI);
263 } else {
264 assert(A.isMask());
265 // RegMask SS flag is preserved by idx().
266 unsigned Idx = Register::stackSlot2Index(Reg: A.idx());
267 const char *Fmt = Idx < 0x10000 ? "%04x" : "%08x";
268 OS << "M#" << format(Fmt, Vals: Idx);
269 }
270}
271
272void PhysicalRegisterInfo::print(raw_ostream &OS, const RegisterAggr &A) const {
273 OS << '{';
274 for (unsigned U : A.units())
275 OS << ' ' << printRegUnit(Unit: U, TRI: &TRI);
276 OS << " }";
277}
278
279bool RegisterAggr::hasAliasOf(RegisterRef RR) const {
280 if (RR.isMask())
281 return Units.anyCommon(RHS: PRI.getMaskUnits(MaskId: RR.Reg));
282
283 for (MCRegUnitMaskIterator U(RR.Reg, &PRI.getTRI()); U.isValid(); ++U) {
284 std::pair<uint32_t, LaneBitmask> P = *U;
285 if ((P.second & RR.Mask).any())
286 if (Units.test(Idx: P.first))
287 return true;
288 }
289 return false;
290}
291
292bool RegisterAggr::hasCoverOf(RegisterRef RR) const {
293 if (RR.isMask()) {
294 BitVector T(PRI.getMaskUnits(MaskId: RR.Reg));
295 return T.reset(RHS: Units).none();
296 }
297
298 for (MCRegUnitMaskIterator U(RR.Reg, &PRI.getTRI()); U.isValid(); ++U) {
299 std::pair<uint32_t, LaneBitmask> P = *U;
300 if ((P.second & RR.Mask).any())
301 if (!Units.test(Idx: P.first))
302 return false;
303 }
304 return true;
305}
306
307RegisterAggr &RegisterAggr::insert(RegisterRef RR) {
308 if (RR.isMask()) {
309 Units |= PRI.getMaskUnits(MaskId: RR.Reg);
310 return *this;
311 }
312
313 for (MCRegUnitMaskIterator U(RR.Reg, &PRI.getTRI()); U.isValid(); ++U) {
314 std::pair<uint32_t, LaneBitmask> P = *U;
315 if ((P.second & RR.Mask).any())
316 Units.set(P.first);
317 }
318 return *this;
319}
320
321RegisterAggr &RegisterAggr::insert(const RegisterAggr &RG) {
322 Units |= RG.Units;
323 return *this;
324}
325
326RegisterAggr &RegisterAggr::intersect(RegisterRef RR) {
327 return intersect(RG: RegisterAggr(PRI).insert(RR));
328}
329
330RegisterAggr &RegisterAggr::intersect(const RegisterAggr &RG) {
331 Units &= RG.Units;
332 return *this;
333}
334
335RegisterAggr &RegisterAggr::clear(RegisterRef RR) {
336 return clear(RG: RegisterAggr(PRI).insert(RR));
337}
338
339RegisterAggr &RegisterAggr::clear(const RegisterAggr &RG) {
340 Units.reset(RHS: RG.Units);
341 return *this;
342}
343
344RegisterRef RegisterAggr::intersectWith(RegisterRef RR) const {
345 RegisterAggr T(PRI);
346 T.insert(RR).intersect(RG: *this);
347 if (T.empty())
348 return RegisterRef();
349 RegisterRef NR = T.makeRegRef();
350 assert(NR);
351 return NR;
352}
353
354RegisterRef RegisterAggr::clearIn(RegisterRef RR) const {
355 return RegisterAggr(PRI).insert(RR).clear(RG: *this).makeRegRef();
356}
357
358RegisterRef RegisterAggr::makeRegRef() const {
359 int U = Units.find_first();
360 if (U < 0)
361 return RegisterRef();
362
363 // Find the set of all registers that are aliased to all the units
364 // in this aggregate.
365
366 // Get all the registers aliased to the first unit in the bit vector.
367 BitVector Regs = PRI.getUnitAliases(U);
368 U = Units.find_next(Prev: U);
369
370 // For each other unit, intersect it with the set of all registers
371 // aliased that unit.
372 while (U >= 0) {
373 Regs &= PRI.getUnitAliases(U);
374 U = Units.find_next(Prev: U);
375 }
376
377 // If there is at least one register remaining, pick the first one,
378 // and consolidate the masks of all of its units contained in this
379 // aggregate.
380
381 int F = Regs.find_first();
382 if (F <= 0)
383 return RegisterRef();
384
385 LaneBitmask M;
386 for (MCRegUnitMaskIterator I(F, &PRI.getTRI()); I.isValid(); ++I) {
387 std::pair<uint32_t, LaneBitmask> P = *I;
388 if (Units.test(Idx: P.first))
389 M |= P.second;
390 }
391 return RegisterRef(F, M);
392}
393
394RegisterAggr::ref_iterator::ref_iterator(const RegisterAggr &RG, bool End)
395 : Owner(&RG) {
396 for (int U = RG.Units.find_first(); U >= 0; U = RG.Units.find_next(Prev: U)) {
397 RegisterRef R = RG.PRI.getRefForUnit(U);
398 Masks[R.Reg] |= R.Mask;
399 }
400 Pos = End ? Masks.end() : Masks.begin();
401 Index = End ? Masks.size() : 0;
402}
403
404raw_ostream &operator<<(raw_ostream &OS, const RegisterAggr &A) {
405 A.getPRI().print(OS, A);
406 return OS;
407}
408
409raw_ostream &operator<<(raw_ostream &OS, const PrintLaneMaskShort &P) {
410 if (P.Mask.all())
411 return OS;
412 if (P.Mask.none())
413 return OS << ":*none*";
414
415 LaneBitmask::Type Val = P.Mask.getAsInteger();
416 if ((Val & 0xffff) == Val)
417 return OS << ':' << format(Fmt: "%04llX", Vals: Val);
418 if ((Val & 0xffffffff) == Val)
419 return OS << ':' << format(Fmt: "%08llX", Vals: Val);
420 return OS << ':' << PrintLaneMask(LaneMask: P.Mask);
421}
422
423} // namespace llvm::rdf
424

source code of llvm/lib/CodeGen/RDFRegisters.cpp