• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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"
12 #include "llvm/CodeGen/MachineFunction.h"
13 #include "llvm/CodeGen/MachineInstr.h"
14 #include "llvm/CodeGen/MachineOperand.h"
15 #include "llvm/CodeGen/TargetRegisterInfo.h"
16 #include "llvm/MC/LaneBitmask.h"
17 #include "llvm/MC/MCRegisterInfo.h"
18 #include "llvm/Support/ErrorHandling.h"
19 #include "llvm/Support/raw_ostream.h"
20 #include <cassert>
21 #include <cstdint>
22 #include <set>
23 #include <utility>
24 
25 using namespace llvm;
26 using namespace rdf;
27 
PhysicalRegisterInfo(const TargetRegisterInfo & tri,const MachineFunction & mf)28 PhysicalRegisterInfo::PhysicalRegisterInfo(const TargetRegisterInfo &tri,
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 
normalize(RegisterRef RR) const98 RegisterRef PhysicalRegisterInfo::normalize(RegisterRef RR) const {
99   return RR;
100 }
101 
getAliasSet(RegisterId Reg) const102 std::set<RegisterId> PhysicalRegisterInfo::getAliasSet(RegisterId Reg) const {
103   // Do not include RR in the alias set.
104   std::set<RegisterId> AS;
105   assert(isRegMaskId(Reg) || TargetRegisterInfo::isPhysicalRegister(Reg));
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) {
115       RegisterId MI = getRegMaskId(RM);
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) {
125     RegisterId MI = getRegMaskId(RM);
126     if (aliasRM(RegisterRef(Reg), RegisterRef(MI)))
127       AS.insert(MI);
128   }
129   return AS;
130 }
131 
aliasRR(RegisterRef RA,RegisterRef RB) const132 bool PhysicalRegisterInfo::aliasRR(RegisterRef RA, RegisterRef RB) const {
133   assert(TargetRegisterInfo::isPhysicalRegister(RA.Reg));
134   assert(TargetRegisterInfo::isPhysicalRegister(RB.Reg));
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 
aliasRM(RegisterRef RR,RegisterRef RM) const163 bool PhysicalRegisterInfo::aliasRM(RegisterRef RR, RegisterRef RM) const {
164   assert(TargetRegisterInfo::isPhysicalRegister(RR.Reg) && isRegMaskId(RM.Reg));
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 
aliasMM(RegisterRef RM,RegisterRef RN) const198 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 
mapTo(RegisterRef RR,unsigned R) const226 RegisterRef PhysicalRegisterInfo::mapTo(RegisterRef RR, unsigned R) const {
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
234                                   : LaneBitmask::getAll();
235     LaneBitmask M = TRI.reverseComposeSubRegIndexLaneMask(Idx, RR.Mask);
236     return RegisterRef(R, M & RCM);
237   }
238   llvm_unreachable("Invalid arguments: unrelated registers?");
239 }
240 
hasAliasOf(RegisterRef RR) const241 bool RegisterAggr::hasAliasOf(RegisterRef RR) const {
242   if (PhysicalRegisterInfo::isRegMaskId(RR.Reg))
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 
hasCoverOf(RegisterRef RR) const254 bool RegisterAggr::hasCoverOf(RegisterRef RR) const {
255   if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) {
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 
insert(RegisterRef RR)269 RegisterAggr &RegisterAggr::insert(RegisterRef RR) {
270   if (PhysicalRegisterInfo::isRegMaskId(RR.Reg)) {
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 
insert(const RegisterAggr & RG)283 RegisterAggr &RegisterAggr::insert(const RegisterAggr &RG) {
284   Units |= RG.Units;
285   return *this;
286 }
287 
intersect(RegisterRef RR)288 RegisterAggr &RegisterAggr::intersect(RegisterRef RR) {
289   return intersect(RegisterAggr(PRI).insert(RR));
290 }
291 
intersect(const RegisterAggr & RG)292 RegisterAggr &RegisterAggr::intersect(const RegisterAggr &RG) {
293   Units &= RG.Units;
294   return *this;
295 }
296 
clear(RegisterRef RR)297 RegisterAggr &RegisterAggr::clear(RegisterRef RR) {
298   return clear(RegisterAggr(PRI).insert(RR));
299 }
300 
clear(const RegisterAggr & RG)301 RegisterAggr &RegisterAggr::clear(const RegisterAggr &RG) {
302   Units.reset(RG.Units);
303   return *this;
304 }
305 
intersectWith(RegisterRef RR) const306 RegisterRef RegisterAggr::intersectWith(RegisterRef RR) const {
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 
clearIn(RegisterRef RR) const316 RegisterRef RegisterAggr::clearIn(RegisterRef RR) const {
317   return RegisterAggr(PRI).insert(RR).clear(*this).makeRegRef();
318 }
319 
makeRegRef() const320 RegisterRef RegisterAggr::makeRegRef() const {
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 
print(raw_ostream & OS) const365 void RegisterAggr::print(raw_ostream &OS) const {
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 
rr_iterator(const RegisterAggr & RG,bool End)372 RegisterAggr::rr_iterator::rr_iterator(const RegisterAggr &RG,
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 }
382