LLVM  9.0.0svn
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 
9 #include "RDFRegisters.h"
10 #include "llvm/ADT/BitVector.h"
15 #include "llvm/MC/LaneBitmask.h"
16 #include "llvm/MC/MCRegisterInfo.h"
19 #include <cassert>
20 #include <cstdint>
21 #include <set>
22 #include <utility>
23 
24 using namespace llvm;
25 using 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(i, &TRI); U.isValid(); ++U)
91  PU.set(*U);
92  }
93  MaskInfos[M].Units = PU.flip();
94  }
95 }
96 
98  return RR;
99 }
100 
101 std::set<RegisterId> PhysicalRegisterInfo::getAliasSet(RegisterId Reg) const {
102  // Do not include RR in the alias set.
103  std::set<RegisterId> AS;
105  if (isRegMaskId(Reg)) {
106  // XXX SLOW
107  const uint32_t *MB = getRegMaskBits(Reg);
108  for (unsigned i = 1, e = TRI.getNumRegs(); i != e; ++i) {
109  if (MB[i/32] & (1u << (i%32)))
110  continue;
111  AS.insert(i);
112  }
113  for (const uint32_t *RM : RegMasks) {
115  if (MI != Reg && aliasMM(RegisterRef(Reg), RegisterRef(MI)))
116  AS.insert(MI);
117  }
118  return AS;
119  }
120 
121  for (MCRegAliasIterator AI(Reg, &TRI, false); AI.isValid(); ++AI)
122  AS.insert(*AI);
123  for (const uint32_t *RM : RegMasks) {
125  if (aliasRM(RegisterRef(Reg), RegisterRef(MI)))
126  AS.insert(MI);
127  }
128  return AS;
129 }
130 
131 bool PhysicalRegisterInfo::aliasRR(RegisterRef RA, RegisterRef RB) const {
134 
135  MCRegUnitMaskIterator UMA(RA.Reg, &TRI);
136  MCRegUnitMaskIterator UMB(RB.Reg, &TRI);
137  // Reg units are returned in the numerical order.
138  while (UMA.isValid() && UMB.isValid()) {
139  // Skip units that are masked off in RA.
140  std::pair<RegisterId,LaneBitmask> PA = *UMA;
141  if (PA.second.any() && (PA.second & RA.Mask).none()) {
142  ++UMA;
143  continue;
144  }
145  // Skip units that are masked off in RB.
146  std::pair<RegisterId,LaneBitmask> PB = *UMB;
147  if (PB.second.any() && (PB.second & RB.Mask).none()) {
148  ++UMB;
149  continue;
150  }
151 
152  if (PA.first == PB.first)
153  return true;
154  if (PA.first < PB.first)
155  ++UMA;
156  else if (PB.first < PA.first)
157  ++UMB;
158  }
159  return false;
160 }
161 
162 bool PhysicalRegisterInfo::aliasRM(RegisterRef RR, RegisterRef RM) const {
164  const uint32_t *MB = getRegMaskBits(RM.Reg);
165  bool Preserved = MB[RR.Reg/32] & (1u << (RR.Reg%32));
166  // If the lane mask information is "full", e.g. when the given lane mask
167  // is a superset of the lane mask from the register class, check the regmask
168  // bit directly.
169  if (RR.Mask == LaneBitmask::getAll())
170  return !Preserved;
171  const TargetRegisterClass *RC = RegInfos[RR.Reg].RegClass;
172  if (RC != nullptr && (RR.Mask & RC->LaneMask) == RC->LaneMask)
173  return !Preserved;
174 
175  // Otherwise, check all subregisters whose lane mask overlaps the given
176  // mask. For each such register, if it is preserved by the regmask, then
177  // clear the corresponding bits in the given mask. If at the end, all
178  // bits have been cleared, the register does not alias the regmask (i.e.
179  // is it preserved by it).
180  LaneBitmask M = RR.Mask;
181  for (MCSubRegIndexIterator SI(RR.Reg, &TRI); SI.isValid(); ++SI) {
182  LaneBitmask SM = TRI.getSubRegIndexLaneMask(SI.getSubRegIndex());
183  if ((SM & RR.Mask).none())
184  continue;
185  unsigned SR = SI.getSubReg();
186  if (!(MB[SR/32] & (1u << (SR%32))))
187  continue;
188  // The subregister SR is preserved.
189  M &= ~SM;
190  if (M.none())
191  return false;
192  }
193 
194  return true;
195 }
196 
197 bool PhysicalRegisterInfo::aliasMM(RegisterRef RM, RegisterRef RN) const {
198  assert(isRegMaskId(RM.Reg) && isRegMaskId(RN.Reg));
199  unsigned NumRegs = TRI.getNumRegs();
200  const uint32_t *BM = getRegMaskBits(RM.Reg);
201  const uint32_t *BN = getRegMaskBits(RN.Reg);
202 
203  for (unsigned w = 0, nw = NumRegs/32; w != nw; ++w) {
204  // Intersect the negations of both words. Disregard reg=0,
205  // i.e. 0th bit in the 0th word.
206  uint32_t C = ~BM[w] & ~BN[w];
207  if (w == 0)
208  C &= ~1;
209  if (C)
210  return true;
211  }
212 
213  // Check the remaining registers in the last word.
214  unsigned TailRegs = NumRegs % 32;
215  if (TailRegs == 0)
216  return false;
217  unsigned TW = NumRegs / 32;
218  uint32_t TailMask = (1u << TailRegs) - 1;
219  if (~BM[TW] & ~BN[TW] & TailMask)
220  return true;
221 
222  return false;
223 }
224 
226  if (RR.Reg == R)
227  return RR;
228  if (unsigned Idx = TRI.getSubRegIndex(R, RR.Reg))
229  return RegisterRef(R, TRI.composeSubRegIndexLaneMask(Idx, RR.Mask));
230  if (unsigned Idx = TRI.getSubRegIndex(RR.Reg, R)) {
231  const RegInfo &RI = RegInfos[R];
232  LaneBitmask RCM = RI.RegClass ? RI.RegClass->LaneMask
235  return RegisterRef(R, M & RCM);
236  }
237  llvm_unreachable("Invalid arguments: unrelated registers?");
238 }
239 
242  return Units.anyCommon(PRI.getMaskUnits(RR.Reg));
243 
244  for (MCRegUnitMaskIterator U(RR.Reg, &PRI.getTRI()); U.isValid(); ++U) {
245  std::pair<uint32_t,LaneBitmask> P = *U;
246  if (P.second.none() || (P.second & RR.Mask).any())
247  if (Units.test(P.first))
248  return true;
249  }
250  return false;
251 }
252 
255  BitVector T(PRI.getMaskUnits(RR.Reg));
256  return T.reset(Units).none();
257  }
258 
259  for (MCRegUnitMaskIterator U(RR.Reg, &PRI.getTRI()); U.isValid(); ++U) {
260  std::pair<uint32_t,LaneBitmask> P = *U;
261  if (P.second.none() || (P.second & RR.Mask).any())
262  if (!Units.test(P.first))
263  return false;
264  }
265  return true;
266 }
267 
270  Units |= PRI.getMaskUnits(RR.Reg);
271  return *this;
272  }
273 
274  for (MCRegUnitMaskIterator U(RR.Reg, &PRI.getTRI()); U.isValid(); ++U) {
275  std::pair<uint32_t,LaneBitmask> P = *U;
276  if (P.second.none() || (P.second & RR.Mask).any())
277  Units.set(P.first);
278  }
279  return *this;
280 }
281 
283  Units |= RG.Units;
284  return *this;
285 }
286 
288  return intersect(RegisterAggr(PRI).insert(RR));
289 }
290 
292  Units &= RG.Units;
293  return *this;
294 }
295 
297  return clear(RegisterAggr(PRI).insert(RR));
298 }
299 
301  Units.reset(RG.Units);
302  return *this;
303 }
304 
306  RegisterAggr T(PRI);
307  T.insert(RR).intersect(*this);
308  if (T.empty())
309  return RegisterRef();
310  RegisterRef NR = T.makeRegRef();
311  assert(NR);
312  return NR;
313 }
314 
316  return RegisterAggr(PRI).insert(RR).clear(*this).makeRegRef();
317 }
318 
320  int U = Units.find_first();
321  if (U < 0)
322  return RegisterRef();
323 
324  auto AliasedRegs = [this] (uint32_t Unit, BitVector &Regs) {
325  for (MCRegUnitRootIterator R(Unit, &PRI.getTRI()); R.isValid(); ++R)
326  for (MCSuperRegIterator S(*R, &PRI.getTRI(), true); S.isValid(); ++S)
327  Regs.set(*S);
328  };
329 
330  // Find the set of all registers that are aliased to all the units
331  // in this aggregate.
332 
333  // Get all the registers aliased to the first unit in the bit vector.
334  BitVector Regs(PRI.getTRI().getNumRegs());
335  AliasedRegs(U, Regs);
336  U = Units.find_next(U);
337 
338  // For each other unit, intersect it with the set of all registers
339  // aliased that unit.
340  while (U >= 0) {
341  BitVector AR(PRI.getTRI().getNumRegs());
342  AliasedRegs(U, AR);
343  Regs &= AR;
344  U = Units.find_next(U);
345  }
346 
347  // If there is at least one register remaining, pick the first one,
348  // and consolidate the masks of all of its units contained in this
349  // aggregate.
350 
351  int F = Regs.find_first();
352  if (F <= 0)
353  return RegisterRef();
354 
355  LaneBitmask M;
356  for (MCRegUnitMaskIterator I(F, &PRI.getTRI()); I.isValid(); ++I) {
357  std::pair<uint32_t,LaneBitmask> P = *I;
358  if (Units.test(P.first))
359  M |= P.second.none() ? LaneBitmask::getAll() : P.second;
360  }
361  return RegisterRef(F, M);
362 }
363 
365  OS << '{';
366  for (int U = Units.find_first(); U >= 0; U = Units.find_next(U))
367  OS << ' ' << printRegUnit(U, &PRI.getTRI());
368  OS << " }";
369 }
370 
372  bool End)
373  : Owner(&RG) {
374  for (int U = RG.Units.find_first(); U >= 0; U = RG.Units.find_next(U)) {
375  RegisterRef R = RG.PRI.getRefForUnit(U);
376  Masks[R.Reg] |= R.Mask;
377  }
378  Pos = End ? Masks.end() : Masks.begin();
379  Index = End ? Masks.size() : 0;
380 }
bool hasCoverOf(RegisterRef RR) const
uint64_t CallInst * C
A common definition of LaneBitmask for use in TableGen and CodeGen.
LaneBitmask reverseComposeSubRegIndexLaneMask(unsigned IdxA, LaneBitmask LaneMask) const
Transform a lanemask given for a virtual register to the corresponding lanemask before using subregis...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
unsigned getSubRegIndex(unsigned RegNo, unsigned SubRegNo) const
For a given register pair, return the sub-register index if the second register is a sub-register of ...
unsigned Reg
bool hasAliasOf(RegisterRef RR) const
unsigned const TargetRegisterInfo * TRI
F(f)
RegisterRef intersectWith(RegisterRef RR) const
unsigned getNumRegUnits() const
Return the number of (native) register units in the target.
RegisterRef clearIn(RegisterRef RR) const
SI optimize exec mask operations pre RA
bool isValid() const
Returns true if this iterator is not yet at the end.
MCRegUnitMaskIterator enumerates a list of register units and their associated lane masks for Reg...
MCSuperRegIterator enumerates all super-registers of Reg.
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:331
int find_next(unsigned Prev) const
find_next - Returns the index of the next set bit following the "Prev" bit.
Definition: BitVector.h:339
static constexpr LaneBitmask getAll()
Definition: LaneBitmask.h:83
iterator_range< regclass_iterator > regclasses() const
Printable printRegUnit(unsigned Unit, const TargetRegisterInfo *TRI)
Create Printable object to print register units on a raw_ostream.
uint32_t size() const
Definition: RDFRegisters.h:60
void print(raw_ostream &OS) const
MCRegUnitRootIterator enumerates the root registers of a register unit.
uint32_t insert(T Val)
Definition: RDFRegisters.h:45
std::set< RegisterId > getAliasSet(RegisterId Reg) const
PhysicalRegisterInfo(const TargetRegisterInfo &tri, const MachineFunction &mf)
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
RegisterAggr & clear(RegisterRef RR)
#define P(N)
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Iterator that enumerates the sub-registers of a Reg and the associated sub-register indices...
RegisterRef normalize(RegisterRef RR) const
MCRegAliasIterator enumerates all registers aliasing Reg.
RegisterRef makeRegRef() const
constexpr bool none() const
Definition: LaneBitmask.h:51
RegisterRef getRefForUnit(uint32_t U) const
Definition: RDFRegisters.h:123
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
RegisterAggr & insert(RegisterRef RR)
MachineOperand class - Representation of each machine instruction operand.
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...
rr_iterator(const RegisterAggr &RG, bool End)
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:211
Representation of each machine instruction.
Definition: MachineInstr.h:64
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
T get(uint32_t Idx) const
Definition: RDFRegisters.h:39
static ValueLatticeElement intersect(const ValueLatticeElement &A, const ValueLatticeElement &B)
Combine two sets of facts about the same value into a single set of facts.
virtual ArrayRef< const uint32_t * > getRegMasks() const =0
Return all the call-preserved register masks defined for this target.
RegisterId getRegMaskId(const uint32_t *RM) const
Definition: RDFRegisters.h:105
#define I(x, y, z)
Definition: MD5.cpp:58
RegisterRef mapTo(RegisterRef RR, unsigned R) const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool isRegMaskId(RegisterId R)
Definition: RDFRegisters.h:101
const uint32_t * getRegMaskBits(RegisterId R) const
Definition: RDFRegisters.h:109
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
IRTranslator LLVM IR MI
bool isValid() const
Check if the iterator is at the end of the list.
RegisterAggr & intersect(RegisterRef RR)