LLVM  6.0.0svn
RDFRegisters.cpp
Go to the documentation of this file.
1 //===- RDFRegisters.cpp ---------------------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "RDFRegisters.h"
11 #include "llvm/ADT/BitVector.h"
16 #include "llvm/MC/LaneBitmask.h"
17 #include "llvm/MC/MCRegisterInfo.h"
20 #include <cassert>
21 #include <cstdint>
22 #include <set>
23 #include <utility>
24 
25 using namespace llvm;
26 using namespace rdf;
27 
29  const MachineFunction &mf)
30  : TRI(tri) {
31  RegInfos.resize(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(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  if (P.second.any()) {
65  UI.Mask = P.second;
66  } else {
67  if (const TargetRegisterClass *RC = RegInfos[F].RegClass)
68  UI.Mask = RC->LaneMask;
69  else
70  UI.Mask = LaneBitmask::getAll();
71  }
72  }
73  }
74  }
75 
76  for (const uint32_t *RM : TRI.getRegMasks())
77  RegMasks.insert(RM);
78  for (const MachineBasicBlock &B : mf)
79  for (const MachineInstr &In : B)
80  for (const MachineOperand &Op : In.operands())
81  if (Op.isRegMask())
82  RegMasks.insert(Op.getRegMask());
83 
84  MaskInfos.resize(RegMasks.size()+1);
85  for (uint32_t M = 1, NM = RegMasks.size(); M <= NM; ++M) {
86  BitVector PU(TRI.getNumRegUnits());
87  const uint32_t *MB = RegMasks.get(M);
88  for (unsigned i = 1, e = TRI.getNumRegs(); i != e; ++i) {
89  if (!(MB[i/32] & (1u << (i%32))))
90  continue;
91  for (MCRegUnitIterator U(i, &TRI); U.isValid(); ++U)
92  PU.set(*U);
93  }
94  MaskInfos[M].Units = PU.flip();
95  }
96 }
97 
99  return RR;
100 }
101 
102 std::set<RegisterId> PhysicalRegisterInfo::getAliasSet(RegisterId Reg) const {
103  // Do not include RR in the alias set.
104  std::set<RegisterId> AS;
106  if (isRegMaskId(Reg)) {
107  // XXX SLOW
108  const uint32_t *MB = getRegMaskBits(Reg);
109  for (unsigned i = 1, e = TRI.getNumRegs(); i != e; ++i) {
110  if (MB[i/32] & (1u << (i%32)))
111  continue;
112  AS.insert(i);
113  }
114  for (const uint32_t *RM : RegMasks) {
116  if (MI != Reg && aliasMM(RegisterRef(Reg), RegisterRef(MI)))
117  AS.insert(MI);
118  }
119  return AS;
120  }
121 
122  for (MCRegAliasIterator AI(Reg, &TRI, false); AI.isValid(); ++AI)
123  AS.insert(*AI);
124  for (const uint32_t *RM : RegMasks) {
126  if (aliasRM(RegisterRef(Reg), RegisterRef(MI)))
127  AS.insert(MI);
128  }
129  return AS;
130 }
131 
132 bool PhysicalRegisterInfo::aliasRR(RegisterRef RA, RegisterRef RB) const {
135 
136  MCRegUnitMaskIterator UMA(RA.Reg, &TRI);
137  MCRegUnitMaskIterator UMB(RB.Reg, &TRI);
138  // Reg units are returned in the numerical order.
139  while (UMA.isValid() && UMB.isValid()) {
140  // Skip units that are masked off in RA.
141  std::pair<RegisterId,LaneBitmask> PA = *UMA;
142  if (PA.second.any() && (PA.second & RA.Mask).none()) {
143  ++UMA;
144  continue;
145  }
146  // Skip units that are masked off in RB.
147  std::pair<RegisterId,LaneBitmask> PB = *UMB;
148  if (PB.second.any() && (PB.second & RB.Mask).none()) {
149  ++UMB;
150  continue;
151  }
152 
153  if (PA.first == PB.first)
154  return true;
155  if (PA.first < PB.first)
156  ++UMA;
157  else if (PB.first < PA.first)
158  ++UMB;
159  }
160  return false;
161 }
162 
163 bool PhysicalRegisterInfo::aliasRM(RegisterRef RR, RegisterRef RM) const {
165  const uint32_t *MB = getRegMaskBits(RM.Reg);
166  bool Preserved = MB[RR.Reg/32] & (1u << (RR.Reg%32));
167  // If the lane mask information is "full", e.g. when the given lane mask
168  // is a superset of the lane mask from the register class, check the regmask
169  // bit directly.
170  if (RR.Mask == LaneBitmask::getAll())
171  return !Preserved;
172  const TargetRegisterClass *RC = RegInfos[RR.Reg].RegClass;
173  if (RC != nullptr && (RR.Mask & RC->LaneMask) == RC->LaneMask)
174  return !Preserved;
175 
176  // Otherwise, check all subregisters whose lane mask overlaps the given
177  // mask. For each such register, if it is preserved by the regmask, then
178  // clear the corresponding bits in the given mask. If at the end, all
179  // bits have been cleared, the register does not alias the regmask (i.e.
180  // is it preserved by it).
181  LaneBitmask M = RR.Mask;
182  for (MCSubRegIndexIterator SI(RR.Reg, &TRI); SI.isValid(); ++SI) {
183  LaneBitmask SM = TRI.getSubRegIndexLaneMask(SI.getSubRegIndex());
184  if ((SM & RR.Mask).none())
185  continue;
186  unsigned SR = SI.getSubReg();
187  if (!(MB[SR/32] & (1u << (SR%32))))
188  continue;
189  // The subregister SR is preserved.
190  M &= ~SM;
191  if (M.none())
192  return false;
193  }
194 
195  return true;
196 }
197 
198 bool PhysicalRegisterInfo::aliasMM(RegisterRef RM, RegisterRef RN) const {
199  assert(isRegMaskId(RM.Reg) && isRegMaskId(RN.Reg));
200  unsigned NumRegs = TRI.getNumRegs();
201  const uint32_t *BM = getRegMaskBits(RM.Reg);
202  const uint32_t *BN = getRegMaskBits(RN.Reg);
203 
204  for (unsigned w = 0, nw = NumRegs/32; w != nw; ++w) {
205  // Intersect the negations of both words. Disregard reg=0,
206  // i.e. 0th bit in the 0th word.
207  uint32_t C = ~BM[w] & ~BN[w];
208  if (w == 0)
209  C &= ~1;
210  if (C)
211  return true;
212  }
213 
214  // Check the remaining registers in the last word.
215  unsigned TailRegs = NumRegs % 32;
216  if (TailRegs == 0)
217  return false;
218  unsigned TW = NumRegs / 32;
219  uint32_t TailMask = (1u << TailRegs) - 1;
220  if (~BM[TW] & ~BN[TW] & TailMask)
221  return true;
222 
223  return false;
224 }
225 
227  if (RR.Reg == R)
228  return RR;
229  if (unsigned Idx = TRI.getSubRegIndex(R, RR.Reg))
230  return RegisterRef(R, TRI.composeSubRegIndexLaneMask(Idx, RR.Mask));
231  if (unsigned Idx = TRI.getSubRegIndex(RR.Reg, R)) {
232  const RegInfo &RI = RegInfos[R];
233  LaneBitmask RCM = RI.RegClass ? RI.RegClass->LaneMask
236  return RegisterRef(R, M & RCM);
237  }
238  llvm_unreachable("Invalid arguments: unrelated registers?");
239 }
240 
243  return Units.anyCommon(PRI.getMaskUnits(RR.Reg));
244 
245  for (MCRegUnitMaskIterator U(RR.Reg, &PRI.getTRI()); U.isValid(); ++U) {
246  std::pair<uint32_t,LaneBitmask> P = *U;
247  if (P.second.none() || (P.second & RR.Mask).any())
248  if (Units.test(P.first))
249  return true;
250  }
251  return false;
252 }
253 
256  BitVector T(PRI.getMaskUnits(RR.Reg));
257  return T.reset(Units).none();
258  }
259 
260  for (MCRegUnitMaskIterator U(RR.Reg, &PRI.getTRI()); U.isValid(); ++U) {
261  std::pair<uint32_t,LaneBitmask> P = *U;
262  if (P.second.none() || (P.second & RR.Mask).any())
263  if (!Units.test(P.first))
264  return false;
265  }
266  return true;
267 }
268 
271  Units |= PRI.getMaskUnits(RR.Reg);
272  return *this;
273  }
274 
275  for (MCRegUnitMaskIterator U(RR.Reg, &PRI.getTRI()); U.isValid(); ++U) {
276  std::pair<uint32_t,LaneBitmask> P = *U;
277  if (P.second.none() || (P.second & RR.Mask).any())
278  Units.set(P.first);
279  }
280  return *this;
281 }
282 
284  Units |= RG.Units;
285  return *this;
286 }
287 
289  return intersect(RegisterAggr(PRI).insert(RR));
290 }
291 
293  Units &= RG.Units;
294  return *this;
295 }
296 
298  return clear(RegisterAggr(PRI).insert(RR));
299 }
300 
302  Units.reset(RG.Units);
303  return *this;
304 }
305 
307  RegisterAggr T(PRI);
308  T.insert(RR).intersect(*this);
309  if (T.empty())
310  return RegisterRef();
311  RegisterRef NR = T.makeRegRef();
312  assert(NR);
313  return NR;
314 }
315 
317  return RegisterAggr(PRI).insert(RR).clear(*this).makeRegRef();
318 }
319 
321  int U = Units.find_first();
322  if (U < 0)
323  return RegisterRef();
324 
325  auto AliasedRegs = [this] (uint32_t Unit, BitVector &Regs) {
326  for (MCRegUnitRootIterator R(Unit, &PRI.getTRI()); R.isValid(); ++R)
327  for (MCSuperRegIterator S(*R, &PRI.getTRI(), true); S.isValid(); ++S)
328  Regs.set(*S);
329  };
330 
331  // Find the set of all registers that are aliased to all the units
332  // in this aggregate.
333 
334  // Get all the registers aliased to the first unit in the bit vector.
335  BitVector Regs(PRI.getTRI().getNumRegs());
336  AliasedRegs(U, Regs);
337  U = Units.find_next(U);
338 
339  // For each other unit, intersect it with the set of all registers
340  // aliased that unit.
341  while (U >= 0) {
342  BitVector AR(PRI.getTRI().getNumRegs());
343  AliasedRegs(U, AR);
344  Regs &= AR;
345  U = Units.find_next(U);
346  }
347 
348  // If there is at least one register remaining, pick the first one,
349  // and consolidate the masks of all of its units contained in this
350  // aggregate.
351 
352  int F = Regs.find_first();
353  if (F <= 0)
354  return RegisterRef();
355 
356  LaneBitmask M;
357  for (MCRegUnitMaskIterator I(F, &PRI.getTRI()); I.isValid(); ++I) {
358  std::pair<uint32_t,LaneBitmask> P = *I;
359  if (Units.test(P.first))
360  M |= P.second.none() ? LaneBitmask::getAll() : P.second;
361  }
362  return RegisterRef(F, M);
363 }
364 
366  OS << '{';
367  for (int U = Units.find_first(); U >= 0; U = Units.find_next(U))
368  OS << ' ' << PrintRegUnit(U, &PRI.getTRI());
369  OS << " }";
370 }
371 
373  bool End)
374  : Owner(&RG) {
375  for (int U = RG.Units.find_first(); U >= 0; U = RG.Units.find_next(U)) {
376  RegisterRef R = RG.PRI.getRefForUnit(U);
377  Masks[R.Reg] |= R.Mask;
378  }
379  Pos = End ? Masks.end() : Masks.begin();
380  Index = End ? Masks.size() : 0;
381 }
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...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
static LaneBitmask getAll()
Definition: LaneBitmask.h:84
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 ...
bool hasAliasOf(RegisterRef RR) const
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:332
int find_next(unsigned Prev) const
find_next - Returns the index of the next set bit following the "Prev" bit.
Definition: BitVector.h:340
Reg
All possible values of the reg field in the ModR/M byte.
iterator_range< regclass_iterator > regclasses() const
uint32_t size() const
Definition: RDFRegisters.h:61
void print(raw_ostream &OS) const
MCRegUnitRootIterator enumerates the root registers of a register unit.
#define T
const RegList & Regs
uint32_t insert(T Val)
Definition: RDFRegisters.h:46
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:52
static const unsigned End
RegisterRef getRefForUnit(uint32_t U) const
Definition: RDFRegisters.h:124
const AMDGPUAS & AS
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)
Printable PrintRegUnit(unsigned Unit, const TargetRegisterInfo *TRI)
Create Printable object to print register units on a raw_ostream.
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:210
Representation of each machine instruction.
Definition: MachineInstr.h:59
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:40
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:106
#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:102
const uint32_t * getRegMaskBits(RegisterId R) const
Definition: RDFRegisters.h:110
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
IRTranslator LLVM IR MI
bool isValid() const
Check if the iterator is at the end of the list.
RegisterAggr & intersect(RegisterRef RR)